Week 14 [2023-07-04 Tue]
We discussed derivatives.
The derivative with respect to a string u of a language L is the set of strings v which, when suffixed onto u, yield a sentence of L. \[D_{u}\ L := \{v \mid uv\in L\}\]
The derivative operator interacts with the monoidal structure of strings:
- \(D_{\epsilon}\ L := L\)
- \(D_{uv}\ L := D_{v}\ (D_{u}\ L)\)
Finally, using derivatives, the membership problem of a language L can be reduced to determining whether a language contains the empty string: \[w \in L \longleftrightarrow \epsilon \in D_{w}\ L\]
One intuitive desideratum on language processing is that it should be incremental, that is, that each word is processed as soon as it is heard. The second of the two properties above ensures that we can use derivatives in this way: \(D_{aw}\ L = D_{w}\ (D_{a}\ L)\). Informally speaking, upon hearing a word a, we can immediately update our information state to \(D_{a}\ L\).
Of course, a language qua potentially infinite set of strings is an inappropriate choice for a representation. Given that we already have a finite representation for an infinite set of strings in the form of a grammar, what we would like is to find an operation \(\delta_{a}\) on grammars that behaves like the derivative operation on languages: \[L(\delta_{a}\ G) = D_{a}\ L(G)\].
Consider a lexical item with the following shape: \(\textrm{w}\mathrel{:} \mathop{\hbox{ =}}\textsf{x}.\mathop{\hbox{ +}}\textsf{y}.\textsf{z}\). This item will have a maximal projection of the following form:
Figure 1: Maximal projection
If we were to try to compute the derivative with respect to a word a, we would need a new set of features, whose job it is to indicate that we are working with something from which a left-most a has been deleted. We would like to determine how to make our w lexical item one of these things, a \({\sf z}^{a}\). Clearly, one way w can be missing its left most a is for the moved item to be missing its left most a: \(\textrm{w}\mathrel{:}\mathop{\hbox{ =}}{\sf x}.\mathop{\hbox{ +}}{\sf y}^{a}.{\sf z}^{a}\). Another possibility however is that this moved expression is actually silent. In this case, if w is equal to a, then we can delete it: \(\epsilon\mathrel{:}\mathop{\hbox{ =}}{\sf x}.\mathop{\hbox{ +}}{\sf y}^{\epsilon}.{\sf z}^{a}\). Finally, if both the mover and the head are silent, then the complement must be missing its leftmost a: \(\textrm{w}\mathrel{:}\mathop{\hbox{ =}}{\sf x}^{a}.\mathop{\hbox{ +}}{\sf y}^{\epsilon}.{\sf z}^{a}\). The three lexical entries which generate a ZP missing its leftmost a are then
- \(\textrm{w}\mathrel{:}\mathop{\hbox{ =}}{\sf x}.\mathop{\hbox{ +}}{\sf y}^{a}.{\sf z}^{a}\)
- \(\epsilon\mathrel{:}\mathop{\hbox{ =}}{\sf x}.\mathop{\hbox{ +}}{\sf y}^{\epsilon}.{\sf z}^{a}\) (as long as \(w = a\))
- \(\textrm{w}\mathrel{:}\mathop{\hbox{ =}}{\sf x}^{a}.\mathop{\hbox{ +}}{\sf y}^{\epsilon}.{\sf z}^{a}\) (as long as \(w = \epsilon\))
In case a lexical item \(\ell = \textrm{w}\mathrel{:}{\sf z}.\mathop{\hbox{ -}}{\sf b}.\mathop{\hbox{ -}}{\sf c}\) has negative movement features, we need to specify in which of these positions it will be pronounced. We adopt a simple (pronounce highest) strategy, which yields the following LI: \(\) \(\ell = \epsilon\mathrel{:}{\sf z}^{\epsilon}.\mathop{\hbox{ -}}{\sf b}^{\epsilon}.\mathop{\hbox{ -}}{\sf c}^{a}\)
Finally, we need to mark up which expressions are silent. Again, we use the original example. Here, the LI would be silent only if all merged or moved expressions were silent, and the LI is itself silent: \(\epsilon\mathrel{:}\mathop{\hbox{ =}}{\sf x}^{\epsilon}.\mathop{\hbox{ +}}{\sf y}^{\epsilon}.{\sf z}^{\epsilon}\).
Homework
Compute \(\delta_{laugh}\ G\), where G consists of the lexical items below:
- \(\textrm{John}\mathrel{:}{\sf d}.\mathop{\hbox{ -}}{\sf k}\)
- \(\textrm{laugh}\mathrel{:}\mathop{\hbox{ =}}{\sf d}.{\sf v}\)
- \(\textrm{will}\mathrel{:}\mathop{\hbox{ =}}{\sf v}.\mathop{\hbox{ +}}{\sf k}.{\sf s}\)
- \(\epsilon\mathrel{:}\mathop{\hbox{ =}}{\sf v}.{\sf v}.\mathop{\hbox{ -}}{\sf top}\)
- \(\epsilon\mathrel{:}\mathop{\hbox{ =}}{\sf s}.\mathop{\hbox{ +}}{\sf top}.{\sf s}\)