GA 1003. Formal Grammars and Languages

\(\newcommand\Alpha{\mathrm{A}} \newcommand\Beta{\mathrm{B}} \newcommand\Epsilon{\mathrm{E}} \newcommand\Zeta{\mathrm{Z}} \newcommand\Eta{\mathrm{H}} \newcommand\Iota{\mathrm{I}} \newcommand\Kappa{\mathrm{K}} \newcommand\Mu{\mathrm{M}} \newcommand\Nu{\mathrm{N}} \newcommand\Omicron{\mathrm{O}} \newcommand\Rho{\mathrm{P}} \newcommand\Tau{\mathrm{T}} \newcommand\Chi{\mathrm{X}} \newcommand\bfalpha{\boldsymbol\alpha } \newcommand\bfbeta{\boldsymbol\beta } \newcommand\bfgamma{\boldsymbol\gamma } \newcommand\bfdelta{\boldsymbol\delta } \newcommand\bfepsilon{\boldsymbol\epsilon } \newcommand\bfzeta{\boldsymbol\zeta } \newcommand\bfeta{\boldsymbol\eta } \newcommand\bftheta{\boldsymbol\theta } \newcommand\bfiota{\boldsymbol\iota } \newcommand\bfkappa{\boldsymbol\kappa } \newcommand\bflambda{\boldsymbol\lambda } \newcommand\bfmu{\boldsymbol\mu } \newcommand\bfnu{\boldsymbol\nu } \newcommand\bfxi{\boldsymbol\xi } \newcommand\bfpi{\boldsymbol\pi } \newcommand\bfrho{\boldsymbol\rho } \newcommand\bfsigma{\boldsymbol\sigma } \newcommand\bftau{\boldsymbol\tau } \newcommand\bfupsilon{\boldsymbol\upsilon } \newcommand\bfphi{\boldsymbol\phi } \newcommand\bfchi{\boldsymbol\chi } \newcommand\bfpsi{\boldsymbol\psi } \newcommand\bfomega{\boldsymbol\omega } \newcommand\N{\mathbb{N}} \newcommand\Z{\mathbb{Z}} \newcommand\Q{\mathbb{Q}} \newcommand\R{\mathbb{R}} \newcommand\True{\mathsf{True}} \newcommand\False{\mathsf{False}} \newcommand\Nothing{\mathsf{Nothing}} \newcommand\Just{\mathsf{Just}} \newcommand\Left{\mathsf{Left}} \newcommand\Right{\mathsf{Right}} \let\mathllap\llap \let\mathrlap\rlap \def\bigsqcap{\mathop{\mathchoice {\lower7mu{\huge\sqcap}} {\lower4mu{\Large\sqcap}} {\lower2mu{\Large\sqcap}} {\lower1mu{\Large\sqcap}} }} \def\bigsqcup{\mathop{\mathchoice {\lower7mu{\huge\sqcup}} {\lower4mu{\Large\sqcup}} {\lower2mu{\Large\sqcup}} {\lower1mu{\Large\sqcup}} }} \def\oh{\mathord{\mathchoice {\small\raise3mu\bigcirc} {\small\raise2mu\bigcirc} {\small\raise1mu\bigcirc} {\small\raise1mu\bigcirc} }} \def\blackoh{\mathord{\mathchoice {\huge\lower2mu\bullet} {\huge\lower2mu\bullet} {\huge\lower1mu\bullet} {\huge\lower2mu\bullet} }} \def\curl{\mathbin{\mathchoice {\mkern-4mu{}^\smallfrown\mkern-7mu} {\mkern-4mu{}^\smallfrown\mkern-7mu} {\mkern+0mu{}^{^\smallfrown}\mkern-4mu} {\mkern+0mu{}^{^\smallfrown}\mkern-3mu} }} \def\desc{\mathord{\mathit{\unicode{x2129}}\mathchoice{\mkern2mu}{\mkern2mu}{\mkern1mu}{\mkern1mu}}} \renewcommand\Box{\mathop{\square}} \renewcommand\Diamond{\mathop{\lozenge}} \newcommand\Circle{\mathop{\oh}} \newcommand\Determ{\mathop{\bigtriangleup}} \newcommand\Indeterm{\mathop{\bigtriangledown}} \newcommand\Would{\mathrel{\square\mkern-2.7mu\raise0.3ex\hbox{$\rightarrow$}}} \newcommand\set[1]{\{\, #1 \,\}} \newcommand\where{\nonscript\;\ifnum\currentgrouptype=16 \middle\fi|\nonscript\;} \def\where{\mid } \newcommand\tuple[1]{\langle\, #1 \,\rangle } \newcommand\paren[1]{\big(\, #1 \,\big)} \newcommand\Set[1]{\left\{\, #1 \,\right\}} \newcommand\Tuple[1]{\left\langle\, #1 \,\right\rangle } \newcommand\Paren[1]{\left(\, #1 \,\right)} \newcommand\Bracket[1]{\left[\, #1 \,\right]} \newcommand\interp[1]{[\![\, #1 \,]\!]} \newcommand\abs[1]{\lvert\, #1 \,\rvert } \newcommand\absabs[1]{\lVert\, #1 \,\rVert } \newcommand\udot{\mathbin{\mathaccent\cdot\cup}} \newcommand\bigudot{\mathop{\mathrlap{\mathchoice{\mkern10mu}{\mkern8mu}{\mkern8mu}{\mkern6mu}\cdot}\bigcup}} \def\udot{\mathbin{\mathchoice {\cup\mkern-9mu{\cdot}\mkern6mu} {\cup\mkern-9mu{\cdot}\mkern5mu} {\cup\mkern-7mu{\cdot}\mkern2mu} {\cup\mkern-6mu{\cdot}\mkern3mu} }} \def\bigudot{\mathbin{\mathchoice {\bigcup\mkern-15mu{\cdot}\mkern10mu} {\bigcup\mkern-13mu{\cdot}\mkern8mu} {\bigcup\mkern-12mu{\cdot}\mkern7mu} {\bigcup\mkern-11mu{\cdot}\mkern7mu} }} \newcommand\Union{\bigcup\limits } \newcommand\Intersect{\bigcap\limits } \newcommand\Vee{\bigvee\limits } \newcommand\Wedge{\bigwedge\limits } \newcommand\Sqcup{\bigsqcup\limits } \newcommand\Sqcap{\bigsqcap\limits } \newcommand\Uplus{\biguplus\limits } \newcommand\Udot{\bigudot\limits } \let\triup\vartriangle \let\tridown\triangledown \let\blacktriup\blacktriangle \let\blacktridown\blacktriangledown \let\trileft\lhd \let\triright\rhd \let\trilefteq\unlhd \let\tririghteq\unrhd \def\blacktrileft{\mathrel{blacktriangleleft}} \def\blacktriright{\mathrel{blacktriangleright}} \let\smalltrileft\triangleleft \let\smalltriright\triangleright \let\smalldiam\diamond \renewcommand\textprime{\ensuremath{{}'}} \newcommand\textcaret{\relax\ifmmode\latin{\^{}}\else\^{}\fi} \def\textcaret{\text{^}} \newcommand\varcaret{\relax\ifmmode\text{\string^}\else\string^\fi} \def\varcaret{^\mathtt{\unicode{x2227}}} \renewcommand\texttilde{\relax\ifmmode\text{\textasciitilde}\else\textasciitilde\fi} \def\texttilde{\text{~}} \providecommand\lt{< } \providecommand\gt{> } \newcommand\eq{= } \let\varempty\emptyset \let\emptyset\varnothing \let\cond\supset \let\horseshoe\supset \newcommand\bicond{\subset\supset } \let\nin\notin \let\se\subseteq \let\union\cup \let\intersect\cap \let\proves\vdash \newcommand\biproves{\dashv\,\vdash } \newcommand\bimodels{\mathbin{{=}\!|{\models}}} \let\forces\Vdash \let\leadstofrom\leftrightsquigarrow \let\wedgeeq\barwedge \let\bareq\veebar \let\trieq\triangleq \let\oast\circledast \let\ocirc\circledcirc \let\odash\circleddash \newcommand\pow[1]{2^{#1}} \newcommand\varpow[1]{\wp(#1)} \newcommand\e[1]{\mathrm{e}^{#1}} \newcommand\corner[1]{\ulcorner #1\urcorner } \newcommand\bind[2][\lambda]{\mathop{#1}\mathchoice{}{}{\mkern-2mu}{\mkern-2mu} #2.\: } \newcommand\restrict[3][\lambda]{\mathop{#1}\mathchoice{}{}{\mkern-2mu}{\mkern-2mu} #2{:} #3.\: } \newcommand\latin[1]{\relax\ifmmode\text{\fontfamily{lmtt}\selectfont #1}\else{\fontfamily{lmtt}\selectfont #1}\fi} \def\latin#1{\texttt{#1}} \newcommand\script[1]{\mathscr{#1}} \newcommand\red[1]{{\color{red}{#1}}} \newcommand\blue[1]{{\color{blue}{#1}}} \newcommand\green[1]{{\color{green}{#1}}} \newcommand\mathsc[1]{\textsc{\lowercase{#1}}} \def\mathsc#1{{\rm\small #1}}\)

The free monoid over an alphabet

As we said, strings are built up out of a collection of primitive "letters" or "words." The standard term in formal discussions for that collection of primitives is an alphabet, and the set of all strings that can be built up from a given alphabet $\Sigma$ is written $\Sigma^*$.

On the page about Algebraic structures, I used the symbol $\mathfrak{S}$ to refer to the set $\set{\mathcal{A},\mathcal{B}}^*$.

The symbol $\Sigma^*$ is similar to some other symbols that are used. $\Sigma^n$ is the set of strings whose length is exactly $n$. So if $\Sigma = \set{\mathcal{A},\mathcal{B}}$, then $\Sigma^0 = \set{\varepsilon}$, $\Sigma^1 = \set{\varepsilon\smalltriright\mathcal{A}, \varepsilon\smalltriright\mathcal{B}}$, $\Sigma^2 = \set{\varepsilon\smalltriright\mathcal{A}\smalltriright\mathcal{A}, \varepsilon\smalltriright\mathcal{A}\smalltriright\mathcal{B}, \varepsilon\smalltriright\mathcal{B}\smalltriright\mathcal{A}, \varepsilon\smalltriright\mathcal{B}\smalltriright\mathcal{B}}$, and so on. Then we can define:

$\Sigma^* = \Union_{n\in\N} \Sigma^n$

Sometimes people talk about the free semigroup $\Sigma^+$. This is just $\Sigma^* - \set{\varepsilon}$, that is, $\Sigma^*$ without the empty string.

We've now seen a variety of superscript notations. There's (a) $\Gamma^3$ to mean $\Gamma\times\Gamma\times\Gamma$, that is, the set of 3-tuples all of whose elements are from $\Gamma$. Then there's (b) $f^3$ to mean $f\circ f\circ f$. Then there's (c) $f^{-1}$ to mean the inverse of $f$, when it exists. Now finally we see $\Sigma^3$ to mean the set of all strings over the alphabet $\Sigma$ whose length is exactly three. You have to just pay attention to track which of these is meant in a given context. (There are also still further common superscript notations; but I'm suppressing them.)

Epp suggests on p. 781 that usage (d) is really the same as usage (a), that is, that strings of length 3 are just 3-tuples from the set $\Sigma$. That involves conflating strings and tuples in the way I discouraged at the start of term.

Note that $\Sigma^*$ consists only of finite strings, though they may be arbitrarily finitely long. The kind of sequence that we defined strings to be has no infinitely long instances. One can sensibly define other notions of sequence that do have infinitely long instances. (Consider a function $f\colon \N \to \Sigma$, where $f(0)$ is the start of the sequence, $f(1)$ comes next, and so on.) But $\Sigma^*$ only contains finite sequences.

$\Sigma^*$ is formally known as the free monoid generated by the alphabet $\Sigma$. People talk that way --- and sometimes I will too --- but really the proper thing to say would be that it's not the set $\Sigma^*$ that's the monoid, but instead $\tuple{\Sigma^*, \curl, \varepsilon}$. The meaning of "generated" here is similar to the meaning I explained in the advanced notes on groups. The meaning of "free monoid" is that every other monoid with the same (or isomorphic) set of generators will be a homomorphism of $\Sigma^*$. That is, they will either be isomorphic to $\Sigma^*$ or they'll be monoids that "simplify" or "partly model" $\Sigma^*$ by discarding some of its structure. (There, I just used $\Sigma^*$ three times to refer to a monoid, when officially I defined it as just being the set that is that monoid's universe.)

Here's something that might help several ideas you've been looking at recently click together. (We discussed this in class on 17 Sept.) Remember the length function we defined on strings? If our strings are built from alphabet $\Sigma$, then that length function will be a homormorphism from the monoid $\tuple{\Sigma^*,\curl,\varepsilon}$ to the monoid $\tuple{\N,+,0}$. Huh? Sure, think it through. The length function takes us from elements of the monoid of strings (that is, particular strings) to elements of the monoid of numbers (particular numbers). It does so in a way that preserves the structure imposed on the strings by the $\curl$ operation, with its identity $\varepsilon$. So the length of $\varepsilon$ is $0$, and the length of $S\curlT$ will be $\operatorname{length}S + \operatorname{length}T$.

In general that will only be a homomorphism, not an isomorphism, because in the case where $\Sigma$ has more than one letter, distinct strings will be mapped onto the same length. So the homomorphism is many-one, that is, not injective.

At the end of class on Sept 17, I mentioned two ways in which the kinds of strings we've been working with so far might leave us unsatisfied.

The first issue is that typically we won't want to be working with all the strings in the free monoid $\Sigma^*$. For example, if $\Sigma$ is an alphabet of English words, we might want to only work with that subset of $\Sigma^*$ which consists of grammatical English sentences. Theorists use the expression formal language as follows: they say that any subset of $\Sigma^*$ counts as a formal language over the alphabet $\Sigma$. This is not the ordinary folk notion of a language. It doesn't say anything about meanings or even anything about syntax. It's just a set of sentences. Another example might be, perhaps I want to work with that subset of $\set{\mathcal{A},\mathcal{B}}^*$ which consists of sentences that begin and end with the same letter. That set would be a different formal language.

The second issue is that the strings we're working with are flat. They all have exactly the same structure: either they're the empty string, or they have an initial string and a final letter. If I concatenate $\mathcal{A}\mathcal{B}$ and $\mathcal{C}\mathcal{B}\mathcal{A}$, I get just the same result as if I concatenate $\mathcal{A}\mathcal{B}\mathcal{C}$ and $\mathcal{B}\mathcal{A}$. For some purposes, that's convenient. For other purposes, it's not. We'd rather keep track of more internal structure in the string. Just look at all the complex structure in the following string:

I don't mean the brackets to be part of the string; they're just signs to help you see the structure.

We especially need to keep track of more structure when strings are syntactically ambigous. For example, consider the string $They~fed~her~rat~poison.$ What this means depends on whether we understand it as grouped like this:

Formal grammars

The centerpiece to this solution is the notion of a formal grammar. In general terms, this will be a mathematically precise description of how larger expressions can be built out of smaller ones. More specifically, it will be a set of (possibly, and usually, recursive) rules for generating strings from a given alphabet. The rules I first presented you with for how to build strings were an example. But typically formal grammars will be more specialized, so that they don't end up generating all the strings in the free monoid for that alphabet. They should just end up generating the strings in the formal language we're interested in (all and only those strings).

I spoke of grammars as generating a set of strings; it's also possible to think of the grammars as providing patterns that match strings in that set (and fail to match other strings). It'll become clearer why both of these perspectives are available as we proceed.

Let's have an example. First let me define, in English, a set of strings built using the alphabet $\set{\mathcal{A}, \mathcal{B}, \mathcal{C}}$. Let a $\mathrm{center}$ be defined so as to include: (i) $\varepsilon$; (ii) the string $\mathcal{B}$ concatenated with a $\mathrm{center}$; and (iii) nothing else. Let a $\mathrm{surround}$ be defined so as to include (iv) the string $\mathcal{A}$ concatenated with a $\mathrm{center}$ concatenated with the string $\mathcal{C}\mathcal{C}$; and (v) nothing else. In other words, $\mathrm{surround}$s are all the strings with an $\mathcal{A}$ followed by 0 or more $\mathcal{B}$s followed by $\mathcal{C}\mathcal{C}$. This set of strings would sometimes be written as $\set{\mathcal{A}\mathcal{B}^n\mathcal{C}\mathcal{C}\where n \ge 0}$.

What do we have here? There are three rules, whose left-hand side and right-hand side are separated by a $\longrightarrow$ symbol. There is a lot of variation in what symbol is used here. Gamut use $\Rightarrow$. I've also seen $\mathbin{::=}$, $\longleftarrow$, and plain $=$. These are just notational choices. Their role is just to separate the left-hand side of the rules from the right-hand sides. These rules are typically called the grammar's rewrite or production rules.

On the right-hand side of each rule, we see a sequence of symbols. Some of these are just literal strings over our alphabet. These are called terminal symbols. The rest are called nonterminal symbols, or syntactic variables, or sometimes syntactic categories. They play a role akin to my schematic Greek letters. They are "holes" in a template that can be filled in with strings. Which strings? Any string that is ultimately generated by or matches the syntactic variable in question. Each of these syntactic variables has to have one or more defining rules in the grammar: that is, rules where that symbol is on the left-hand side. Those rules will specify (perhaps in a complex recursive way) which strings count as generated by or match that symbol. For example, in the above grammar, the symbol $\mathrm{center}$ counts as matching any string consisting of 0 or more $\mathcal{B}$s. Any such string can fill in the hole marked by the symbol $\mathrm{center}$ on the right-hand side of any rule.

The strings this grammar generates or matches consist of 0 or more $\mathcal{A}$s followed by 0 or more $\mathcal{B}$s. Sometimes this set of strings is written as $\set{\mathcal{A}^m \mathcal{B}^n \where m \ge 0, n \ge 0}$.

Before I explain this grammar, see if you can figure out for yourself what the difference is between the set of strings it generates or matches, and those generated or matched by the preceding grammar.

The answer is that this grammar generates the set of strings $\set{\mathcal{A}^m \mathcal{B}^m \where m \ge 0}$: that is, strings that consist of 0 or more $\mathcal{A}$s followed by the same number of $\mathcal{B}$s.

These two grammars, and the two languages they generate, are importantly different.

The simplest grammars are called regular. These have to have a form where every rhs consists of entirely of terminal symbols, optionally followed by a single syntactic variable. (Alternatively, you could have the syntactic variables coming at the beginning; but whichever style you choose has to be applied consistently across the whole grammar. If the syntactic variables sometimes comes at the start of a rhs, and other times at the end, then the grammar is not regular.)

Our grammar for the $\mathcal{A}^m\mathcal{B}^n$ language (where the syntactic variables were named $\mathrm{pre}$ and $\mathrm{post}$) meets these criteria. (The rhs of the second rule can be rewritten as $\varepsilon\: \mathrm{post}$, thus satisfying the letter of the requirement that the syntactic variable follow some terminals.)

But our grammar for the $\mathcal{A}^m\mathcal{B}^m$ language does not meet them.

Now, it can happen that two different grammars end up generating all the same strings. So the mapping from grammars to the formal languages they determine can be many-one. This is important because grammars can have different theoretically interesting properties; so it tells us you can't directly read those properties off of a formal language. Potentially, that language might be generated by some grammars that have the property in question, and also by some grammars that lack it.

So in particular, it could be, for all we've seen so far, that though our $\mathrm{early}$/$\mathrm{late}$ grammar is not regular, there is some other grammar that is regular and that generates or matches exactly the same language, the set of strings $\set{\mathcal{A}^m \mathcal{B}^m \where m \ge 0}$. However, an important result in this field is that this is not so. No regular grammar can generate or match exactly that set of strings. Hence that set is called a non-regular language.

Our $\mathrm{early}$/$\mathrm{late}$ grammar does match those strings, though; and grammars of that form are called context-free grammars (sometimes abbreviated CFG). The "context" here doesn't have anything to do with what's needed to fix the reference of English expressions like "now" and "that dog." It means the rules for each syntactic variable can be given in a way that ignores their surrounding linguistic context or neighborhood, that is, what symbols come before or after them. We can just say how the symbol $\mathrm{late}$ should be expanded or unpacked, period. We don't have to say: it should be expanded this way when it comes after symbol so-and-so, but unpacked this other way when it comes after symbol such-and-such. The rhs of the rules in a context-free grammar can contain any sequence of terminal symbols and syntactic variables.

As you might guess, for some sets of strings even this will not be adequate. There are some sets of strings that can't even be generated even by a context-free grammar. Here are some examples:

There are also more powerful categories of grammars; two well-known ones are called context-sensitive and type 0 grammars. These categories come from Chomsky. There are also various finer subdivisions of the categories we've described so far, and some kinds of grammars (for example, PEG grammars) that cross-cut some of the categories laid out here. You can read up about the details on your own if you're interested. Lucas Champollion in linguistics may teach a class on these issues someday soon.

Patterns

There are some notational shortcuts or conveniences that one often sees in formal grammars. Recall our first grammar:

One shortcut would be to write the two rules for $\mathrm{center}$ on a single line, like this:

The $|$ divider is part of the grammar's notation. It doesn't mean the literal string or letter $|$, which may or may not be part of our alphabet. If we wanted to refer to that literal letter, we'd have to use some other convention, for instance we might write:

to say that $\mathrm{fence}$s are strings of 0 or more sequential $|$s. But to keep things simple, I will suppose that none of the special characters in our grammar's notation also appear in our alphabet.

Another shorthand we might adopt is to use the symbol "$*$" to mean 0 or more of the preceding. And we might add in parentheses as well, so that "the preceding" can mean a chunk of stuff. Using "$*$", our rule for $\mathrm{center}$ can be written as:

Sometimes the symbol "$+$" is used to mean 1 or more of the preceding. (Compare the superscripts on $\Sigma^*$ and $\Sigma^+$.) Each of the three following rules would then be equivalent:

Similarly, sometimes the symbol "$?$" is used to mean 0 or 1 of the preceding. And, as I mentioned, parentheses can sometimes be used to save us from having to write a separate rule. So the following grammar:

With enough of these conventions, you may be able to express many grammars all in a single rule. We can call these "patterns." For some purposes, having everything as a single pattern may be more useful; for other purposes, having everything as a set of rules with few of these extra shorthands will be easier to theorize about.

Epp describes a pattern format starting on pp. 783 of her selection. It does not essentially differ from the system with the "shortcuts" described above. (It's just that some of those shortcuts would be defined in terms of others.) Epp calls these "regular expression patterns," often abbreviated as regexes or regexps. The patterns Epp describes, introduced by the logician Kleene, are interdefinable with the notion of a regular grammar that we introduced above. Note that you should only assume this to be true for that specific variety of regex. Many contemporary programming languages or interfaces provide facilities they call "regular expressions" but which are more powerful than regular grammars. (The regex patterns in the Perl programming language are in fact Turing complete. Don't worry if you don't yet know what that means; we'll explain it later.)

Let's take a look at pp. 25-26 of Sider. He lists some "primitive vocabulary" for the language of propositional logic (PL). This is an alphabet. In fact it contains infinitely many letters, including $P, P_1, P_2, \dots$. To make things a bit easier for us, I'll vary this and instead use $P, P', P'', \dots$.

Next Sider gives us a "definition of wffs" for PL. Wtf is a wff? Well, what we're doing with our grammars is we're taking the whole big unconstrained set of sentences $\Sigma^*$ and we're selecting a proper subset of them as targets of interest. We can call those the well-formed strings or expressions. When we're doing logic, we're often interested especially in the expressions we call formulas. These are things whose syntactic role is like a sentence, but they are allowed to contain "free variables" like $x$. (Another sort of expression are terms, whose syntactic role is like a name or pronoun.) When logicians are talking about well-formed formulas, they abbreviate that as wff (pronounced "whoof").

How would we write this using the apparatus we've been looking at? Here's one way:

I've made the $\prime$, $($, $\horseshoe$, $)$, and $\neg$ symbols bold and blue to signal that these are literal strings, not parts of our grammar notation.

The alphabet we're using here only has a finite number of letters. We include $P$, $Q$, and $R$ in the language, and also the single letter $\prime$. $P$ counts as a $\mathrm{sent}$, but so too do $P'$, $P''$, and so on.