Generation

How should we state the relationship between a grammar and a language? We’ll call it generation: a grammar $G$ generates a language $L$ when $G$ describes that language. We write this relation as $\mathbb{L}(G)=L$, where $\mathbb{L}$ maps grammars to languages.

The word generation can sound procedural, but our definition is declarative. Saying that $G$ generates $L$ does not yet tell us how to enumerate the strings in $L$ or how to recognize them. It says which language $G$ describes.

Example: regular expressions

We’ve already seen one kind of grammar under this definition: regular expressions. Remember that regular expressions $R(\Sigma)$ on $\Sigma$ are themselves strings in a metalanguage whose alphabet contains $\Sigma$ together with symbols such as $\epsilon$, $\emptyset$, $\cup$, $\circ$, parentheses, and $*$. We define these expressions recursively.

$\rho$ is a regular expression if and only if:

$\rho \in \Sigma \cup \{\epsilon, \emptyset\}$
$\rho$ is $(\rho_1 \cup \rho_2)$ for some regular expressions $\rho_1$ and $\rho_2$
$\rho$ is $(\rho_1 \circ \rho_2)$ for some regular expressions $\rho_1$ and $\rho_2$
$\rho$ is $\rho_1^*$ for some regular expression $\rho_1$

We can generate all the regular expressions given an alphabet.

Regular expressions so defined evaluate to sets of strings on $\Sigma$, i.e. languages on $\Sigma$. Another way of saying this is that a regular expression on $\Sigma$ describes a language on $\Sigma$.

We can define this evaluation procedure formally as a function $\text{eval}: R(\Sigma) \rightarrow 2^{\Sigma^*}$, where $R(\Sigma)$ is the set of regular expressions on $\Sigma$.

$\text{eval}(\rho) = \begin{cases}\{\} & \text{if } \rho = \emptyset \\\{\epsilon\} & \text{if } \rho = \epsilon \\ \{\rho\} & \text{if } \rho \in \Sigma\\ \text{eval}(\rho_1) \circ \text{eval}(\rho_2) & \text{if } \rho = (\rho_1 \circ \rho_2) \\ \text{eval}(\rho_1) \cup \text{eval}(\rho_2) & \text{if } \rho = (\rho_1 \cup \rho_2)\\ \bigcup_{i = 0}^\infty \text{eval}(\rho_1)^i & \text{if } \rho = \rho_1^*\\ \end{cases}$

In the concatenation clause, $A\circ B=\{xy\mid x\in A\text{ and }y\in B\}$. This is language concatenation, not the Cartesian product $A\times B$, whose members would be ordered pairs.

Each regular expression is thus a grammar; the set of all regular expressions is a class of grammars; and $\text{eval}$ is an implementation of $\mathbb{L}$. We will call the class of languages $\mathcal{R}$ generated by the regular expressions the regular languages: \[\mathcal{R} \equiv \mathbb{L}(R(\Sigma)) = \{\mathbb{L}(r) \mid r \in R(\Sigma)\} = \{\text{eval}(r) \mid r \in R(\Sigma)\}\]

We will study these languages in depth because, as I mentioned before, the string languages needed for phonological generalizations appear to fall within the regular class. To study them, it will be useful to introduce a class of grammars that generates exactly the same languages as regular expressions. These grammars are known as finite state automata.

We will refer to the condition $\mathbb{L}(\mathcal{G}_1)=\mathbb{L}(\mathcal{G}_2)$ for grammar classes $\mathcal{G}_1$ and $\mathcal{G}_2$ as weak equivalence or equivalence in weak generative capacity. We will discuss strong equivalence later. First, though, we should ask why we care about classes of grammars at all.

--- title: Generation --- How should we state the relationship between a grammar and a language? We'll call it *generation*: a grammar $G$ generates a language $L$ when $G$ describes that language. We write this relation as $\mathbb{L}(G)=L$, where $\mathbb{L}$ maps grammars to languages. The word *generation* can sound procedural, but our definition is [declarative](https://en.wikipedia.org/wiki/Declarative_programming). Saying that $G$ generates $L$ does not yet tell us how to enumerate the strings in $L$ or how to recognize them. It says which language $G$ describes. ## Example: regular expressions We've already seen one kind of grammar under this definition: regular expressions. Remember that regular expressions $R(\Sigma)$ on $\Sigma$ are themselves strings in a metalanguage whose alphabet contains $\Sigma$ together with symbols such as $\epsilon$, $\emptyset$, $\cup$, $\circ$, parentheses, and $*$. We define these expressions recursively. $\rho$ is a regular expression if and only if: 1. $\rho \in \Sigma \cup \{\epsilon, \emptyset\}$ 2. $\rho$ is $(\rho_1 \cup \rho_2)$ for some regular expressions $\rho_1$ and $\rho_2$ 3. $\rho$ is $(\rho_1 \circ \rho_2)$ for some regular expressions $\rho_1$ and $\rho_2$ 4. $\rho$ is $\rho_1^*$ for some regular expression $\rho_1$ We can generate all the regular expressions given an alphabet. Regular expressions so defined *evaluate* to sets of strings on $\Sigma$, i.e. languages on $\Sigma$. Another way of saying this is that a regular expression on $\Sigma$ *describes* a language on $\Sigma$. We can define this evaluation procedure formally as a function $\text{eval}: R(\Sigma) \rightarrow 2^{\Sigma^*}$, where $R(\Sigma)$ is the set of regular expressions on $\Sigma$. $\text{eval}(\rho) = \begin{cases}\{\} & \text{if } \rho = \emptyset \\\{\epsilon\} & \text{if } \rho = \epsilon \\ \{\rho\} & \text{if } \rho \in \Sigma\\ \text{eval}(\rho_1) \circ \text{eval}(\rho_2) & \text{if } \rho = (\rho_1 \circ \rho_2) \\ \text{eval}(\rho_1) \cup \text{eval}(\rho_2) & \text{if } \rho = (\rho_1 \cup \rho_2)\\ \bigcup_{i = 0}^\infty \text{eval}(\rho_1)^i & \text{if } \rho = \rho_1^*\\ \end{cases}$ In the concatenation clause, $A\circ B=\{xy\mid x\in A\text{ and }y\in B\}$. This is language concatenation, not the Cartesian product $A\times B$, whose members would be ordered pairs. Each regular expression is thus a grammar; the set of all regular expressions is a class of grammars; and $\text{eval}$ is an implementation of $\mathbb{L}$. We will call the class of languages $\mathcal{R}$ generated by the regular expressions the *regular languages*: $$\mathcal{R} \equiv \mathbb{L}(R(\Sigma)) = \{\mathbb{L}(r) \mid r \in R(\Sigma)\} = \{\text{eval}(r) \mid r \in R(\Sigma)\}$$ We will study these languages in depth because, as I mentioned before, the string languages needed for phonological generalizations appear to fall within the regular class. To study them, it will be useful to introduce a class of grammars that generates exactly the same languages as regular expressions. These grammars are known as *finite state automata*. We will refer to the condition $\mathbb{L}(\mathcal{G}_1)=\mathbb{L}(\mathcal{G}_2)$ for grammar classes $\mathcal{G}_1$ and $\mathcal{G}_2$ as *weak equivalence* or *equivalence in weak generative capacity*. We will discuss *strong equivalence* later. First, though, we should ask why we care about classes of grammars at all.