Phonological rewrite rules

The rewrite rules introduced in The Sound Pattern of English (Chomsky and Halle 1968) have the following form:

\[A \rightarrow B\;/\;C\_D\]

The rule replaces a target $A$ with $B$ when $A$ occurs after the left context $C$ and before the right context $D$. The target, replacement, and contexts may each denote a set of strings rather than a single string.

Rules as relations

What should a rewrite rule do to a complete string? It does not merely recognize strings containing $CAD$. It defines a relation between a complete input string and a complete output string. For a mandatory rule, every eligible occurrence of $A$ must be replaced, while every symbol outside the target must be copied.

We will call this relation the context-dependent replacement relation (CDR relation). If $\rho$, $\phi$, $\lambda$, and $\omega$ denote the target, replacement, left context, and right context, respectively, we write it as

\[\operatorname{CDR}(\rho \rightarrow \phi\;/\;\lambda\_\omega).\]

The basic result is that the CDR relation is rational when $\rho$, $\phi$, $\lambda$, and $\omega$ are regular and the rule uses one of the noncyclic application modes covered by the compilation scheme. Thus, it can be represented by an FST (Kaplan and Kay 1994). This scope restriction matters: unrestricted cyclic reapplication may let a rule repeatedly rewrite material created on an earlier pass, producing a nonregular relation (Kaplan and Kay 1994).

This result does not say that the compilation is as simple as finding $\lambda\rho\omega$ and substituting $\phi$. The transducer must decide where a match begins, preserve the contexts without rewriting them, handle overlapping matches, and specify whether application proceeds from left to right or from right to left. These choices are part of the rule definition.

Compiling a rule

Kaplan and Kay’s construction uses temporary boundary markers to separate the contexts from the target (Kaplan and Kay 1994). At a high level, compilation proceeds in four steps:

mark positions that satisfy the right-context condition;
retain only markers that also satisfy the left-context condition;
replace the material between the surviving markers; and
remove the markers.

Each step is a rational relation, so their composition is also a rational relation. Mohri and Sproat refine this strategy by factoring the marker and filter machines so that the resulting compiler handles directionality and overlapping applications more efficiently (Mohri and Sproat 1996). The full construction is beyond what we need here; the point for current purposes is that rule compilation is an application of composition, not a new formal operation.

How does the four-stage construction preserve the rule’s conditions? After the first stage, a candidate marker occurs at every position from which the right context $\omega$ can begin. Because $\omega$ is regular, a finite automaton can track exactly this condition. The second stage retains a candidate only when the material before the target satisfies the regular left context $\lambda$. So the marker invariant is:

A target boundary survives the two filters exactly when that occurrence of $\rho$ has both the required left context and the required right context.

The replacement stage changes only material delimited by surviving markers. Thus, every replacement it makes is licensed by the rule, while the copy transitions preserve all material outside a licensed target. The final stage erases only the administrative markers. This proves soundness: every input-output pair in the compiled relation is a legal application of the rule.

Now check completeness. Take any legal application of the rule and one of its replaced targets. The target has the stated right context, so the first machine marks it. It also has the stated left context, so the second machine retains that marker. The replacement machine includes the corresponding $\rho:\phi$ path, and the cleanup machine removes its markers. Repeating this reasoning for every replaced target gives the legal input-output pair. The compiled relation thus contains every legal application. Since each stage is rational and rational relations are closed under composition, the sound and complete result is rational.

Directionality and overlap conventions determine which markers count as a jointly legal application. They change the filter relation, but not this proof structure.

Question

Why do we need temporary markers? Why not build an FST that replaces $A$ whenever it has just read $C$?

Answer

The left context alone is not enough. The machine must also know that the material after $A$ belongs to $D$, and it may need to delay the replacement decision until that right context has been checked. Markers let separate finite state machines record and filter candidate boundaries before the replacement is made.

Final devoicing

Let $D=\{b,d,g,v,z,\text{ʒ}\}$ be the voiced obstruents and let $\operatorname{devoice}$ map each member of $D$ to its voiceless counterpart. German final devoicing can be stated schematically as

\[D \rightarrow \operatorname{devoice}(D)\;/\;\_\#.\]

An FST compiled from this rule copies every segment except a voiced obstruent immediately before the word boundary. Thus, an input ending in /d/ is paired with an output ending in [t], while a medial /d/ is copied.

Vowel harmony

Suppose that $E$ is an underspecified suffix vowel, $V_f=\{e,i,ö,ü\}$ is the set of front vowels, $V_b=\{a,ı,o,u\}$ is the set of back vowels, and $C$ is the consonant inventory. A two-way backness harmony can be stated with two rules:

\[ \begin{aligned} E &\rightarrow e\;/\;V_fC^*\_ \\ E &\rightarrow a\;/\;V_bC^*\_. \end{aligned} \]

The regular expressions in the left contexts allow the transducer to find the most recent vowel before the suffix. The union of the two compiled relations handles the two harmonic classes only after each relation is restricted to inputs in its stated harmonic domain. Without that restriction, the relation for the inapplicable rule could contribute an identity output for $E$. Equivalently, a compiler can combine the two context-replacement alternatives into one mandatory relation.

Ordering rules

If $T_1$ compiles the first rule in a derivation and $T_2$ compiles the second, the ordered grammar is $T_2 \circ T_1$. The output of $T_1$ is an intermediate representation that serves as the input to $T_2$.

This use of composition is important. Compiling each rule separately preserves the generalization stated by that rule; composing a finite ordered sequence of rule relations yields one rational relation for the grammar as a whole (Kaplan and Kay 1994). We turn next to cases in which the intermediate representation differs in a consequential way from the surface form.

References

Chomsky, Noam, and Morris Halle. 1968. The Sound Pattern of English. Harper & Row.

Kaplan, Ronald M., and Martin Kay. 1994. “Regular Models of Phonological Rule Systems.” Computational Linguistics 20 (3): 331–78. https://aclanthology.org/J94-3001/.

Mohri, Mehryar, and Richard Sproat. 1996. “An Efficient Compiler for Weighted Rewrite Rules.” 34th Annual Meeting of the Association for Computational Linguistics (Santa Cruz, California, USA), 231–38. https://doi.org/10.3115/981863.981894.

--- title: Phonological rewrite rules bibliography: ../../references.bib --- The rewrite rules introduced in *The Sound Pattern of English* [@chomsky1968sound] have the following form: $$A \rightarrow B\;/\;C\_D$$ The rule replaces a target $A$ with $B$ when $A$ occurs after the left context $C$ and before the right context $D$. The target, replacement, and contexts may each denote a set of strings rather than a single string. ## Rules as relations What should a rewrite rule do to a complete string? It does not merely recognize strings containing $CAD$. It defines a relation between a complete input string and a complete output string. For a mandatory rule, every eligible occurrence of $A$ must be replaced, while every symbol outside the target must be copied. We will call this relation the **context-dependent replacement relation** (CDR relation). If $\rho$, $\phi$, $\lambda$, and $\omega$ denote the target, replacement, left context, and right context, respectively, we write it as $$\operatorname{CDR}(\rho \rightarrow \phi\;/\;\lambda\_\omega).$$ The basic result is that the CDR relation is rational when $\rho$, $\phi$, $\lambda$, and $\omega$ are regular and the rule uses one of the noncyclic application modes covered by the compilation scheme. Thus, it can be represented by an FST [@kaplan1994regular]. This scope restriction matters: unrestricted cyclic reapplication may let a rule repeatedly rewrite material created on an earlier pass, producing a nonregular relation [@kaplan1994regular]. This result does not say that the compilation is as simple as finding $\lambda\rho\omega$ and substituting $\phi$. The transducer must decide where a match begins, preserve the contexts without rewriting them, handle overlapping matches, and specify whether application proceeds from left to right or from right to left. These choices are part of the rule definition. ## Compiling a rule Kaplan and Kay's construction uses temporary boundary markers to separate the contexts from the target [@kaplan1994regular]. At a high level, compilation proceeds in four steps: 1. mark positions that satisfy the right-context condition; 2. retain only markers that also satisfy the left-context condition; 3. replace the material between the surviving markers; and 4. remove the markers. Each step is a rational relation, so their composition is also a rational relation. Mohri and Sproat refine this strategy by factoring the marker and filter machines so that the resulting compiler handles directionality and overlapping applications more efficiently [@mohri1997finite]. The full construction is beyond what we need here; the point for current purposes is that rule compilation is an application of composition, not a new formal operation. How does the four-stage construction preserve the rule's conditions? After the first stage, a candidate marker occurs at every position from which the right context $\omega$ can begin. Because $\omega$ is regular, a finite automaton can track exactly this condition. The second stage retains a candidate only when the material before the target satisfies the regular left context $\lambda$. So the **marker invariant** is: > A target boundary survives the two filters exactly when that occurrence of $\rho$ has both the required left context and the required right context. The replacement stage changes only material delimited by surviving markers. Thus, every replacement it makes is licensed by the rule, while the copy transitions preserve all material outside a licensed target. The final stage erases only the administrative markers. This proves soundness: every input-output pair in the compiled relation is a legal application of the rule. Now check completeness. Take any legal application of the rule and one of its replaced targets. The target has the stated right context, so the first machine marks it. It also has the stated left context, so the second machine retains that marker. The replacement machine includes the corresponding $\rho:\phi$ path, and the cleanup machine removes its markers. Repeating this reasoning for every replaced target gives the legal input-output pair. The compiled relation thus contains every legal application. Since each stage is rational and rational relations are closed under composition, the sound and complete result is rational. Directionality and overlap conventions determine which markers count as a jointly legal application. They change the filter relation, but not this proof structure. ::: {.callout-caution} ## Question Why do we need temporary markers? Why not build an FST that replaces $A$ whenever it has just read $C$? ::: ::: {.callout-tip collapse=true} ## Answer The left context alone is not enough. The machine must also know that the material after $A$ belongs to $D$, and it may need to delay the replacement decision until that right context has been checked. Markers let separate finite state machines record and filter candidate boundaries before the replacement is made. ::: ## Final devoicing Let $D=\{b,d,g,v,z,\text{ʒ}\}$ be the voiced obstruents and let $\operatorname{devoice}$ map each member of $D$ to its voiceless counterpart. German final devoicing can be stated schematically as $$D \rightarrow \operatorname{devoice}(D)\;/\;\_\#.$$ An FST compiled from this rule copies every segment except a voiced obstruent immediately before the word boundary. Thus, an input ending in /d/ is paired with an output ending in [t], while a medial /d/ is copied. ## Vowel harmony Suppose that $E$ is an underspecified suffix vowel, $V_f=\{e,i,ö,ü\}$ is the set of front vowels, $V_b=\{a,ı,o,u\}$ is the set of back vowels, and $C$ is the consonant inventory. A two-way backness harmony can be stated with two rules: $$ \begin{aligned} E &\rightarrow e\;/\;V_fC^*\_ \\ E &\rightarrow a\;/\;V_bC^*\_. \end{aligned} $$ The regular expressions in the left contexts allow the transducer to find the most recent vowel before the suffix. The union of the two compiled relations handles the two harmonic classes only after each relation is restricted to inputs in its stated harmonic domain. Without that restriction, the relation for the inapplicable rule could contribute an identity output for $E$. Equivalently, a compiler can combine the two context-replacement alternatives into one mandatory relation. ## Ordering rules If $T_1$ compiles the first rule in a derivation and $T_2$ compiles the second, the ordered grammar is $T_2 \circ T_1$. The output of $T_1$ is an intermediate representation that serves as the input to $T_2$. This use of composition is important. Compiling each rule separately preserves the generalization stated by that rule; composing a finite ordered sequence of rule relations yields one rational relation for the grammar as a whole [@kaplan1994regular]. We turn next to cases in which the intermediate representation differs in a consequential way from the surface form.