Context-free Grammars and Languages

Regular is not enough

So far, we’ve been focusing on regular languages which are sets built from individual strings via a finite combination of concatenation, union, and repetition (Kleene closure.) You can be a lot of interesting languages in this way, but they’re fairly limited. In particular, we’ve seen the language \{0^n1^n \mid n \geq 0\} is not regular. Another nonregular language is the set of strings consisting of balanced parentheses. Even the set of regular expressions which we use to concisely describe regular languages is, itself, not regular.

If we want to recognize more interesting languages such as the regular expressions, we need something more than aforementioned basic operations. In particular, we need to introduce an alternative to basic repetition of a single language. We need to introduce unbounded recursion.

Specifically, we’re going to discuss a model for generating a language called a context-free grammar. Context-free grammars in their modern form were formalized to model the basic structure of natural human languages. I’ll use this motivation to informally explain how they work.

The grammar below shows how to take the parts you might see in a sentence and build them recursively using other or even the same kinds of parts you might see in a sentence. A grammar describing the set of sentences formed from a finite set of English words For example, a sentence is a noun phrase followed by a verb phrase followed by another noun phrase. In turn, a noun phrase is an adjective phrase followed by a noun. For an adjective phrase, you actually have some options:

We keep recursively applying these rules to take things seen on the left of the arrows and replace them with the things they are pointing to one the right. For example: \begin{align*} \langle \text{sentence} \rangle &\leadsto \langle \textbf{noun phrase} \rangle \langle \textbf{verb phrase} \rangle \langle \textbf{noun phrase} \rangle \\ &\leadsto \langle \textbf{adjective phrase} \rangle \langle \textbf{noun} \rangle \langle \text{verb phrase} \rangle \langle \text{noun phrase} \rangle \\ &\leadsto \langle \textbf{adjective phrase} \rangle \langle \textbf{adjective} \rangle \langle \text{noun} \rangle \langle \text{verb phrase} \rangle \langle \text{noun phrase} \rangle \\ &\leadsto \langle \textbf{posessive} \rangle \langle \text{adjective} \rangle \langle \text{noun} \rangle \langle \text{verb phrase} \rangle \langle \text{noun phrase} \rangle \end{align*}

Eventually, you end up getting to individual words for which we have no rules. Those can stay as they are. \begin{align*} &\leadsto \langle \text{posessive} \rangle \langle \text{adjective} \rangle \langle \text{noun} \rangle \langle \text{verb phrase} \rangle \langle \text{noun phrase} \rangle \\ &\leadsto \textbf{your } \langle \text{adjective} \rangle \langle \text{noun} \rangle \langle \text{verb phrase} \rangle \langle \text{noun phrase} \rangle \\ &\leadsto \text{your } \textbf{furious } \langle \text{noun} \rangle \langle \text{verb phrase} \rangle \langle \text{noun phrase} \rangle \end{align*}

And when you have nothing but the individual words, you have your sentence. \begin{align*} &\leadsto \text{your } \text{furious } \langle \text{noun} \rangle \langle \text{verb phrase} \rangle \langle \text{noun phrase} \rangle \\ &\leadsto^* \text{your furious green time lord barely mangled my dog's trousers} \end{align*}

Depending on which choices we made along the way (maybe I just wanted an article for my adjective phrase), you’ll get different parse trees and sentences.

It might help to visualize the process in a parse tree as so: An in-order traversal of the leaves gives you the final sentence. A parse tree describing the full derivation of the above sentence

In computer science, we typically see grammars come up in programming language specifications. You can have a non-terminal that represents all expressions and another for all while loops, for example. You can have a terminal for each literal or variable name. The entire grammar succinctly explains the syntax of valid programs (but not their semantics; you have to actually write English or use a more complicated mathematical language for that.)

Formal definitions

Just like we did for DFAs and NFAs, we can define context-free grammars as a collection of sets and functions. Precisely, context-free grammar (CFG) consists of the following components:

Normally, we write the rules compactly by combining the right sides of all rules for each non-terminal into one list with alternatives separated by vertical bars. For example, here’s a set of eight production rules involving two terminals \Sigma = \{0, 1\} and four non-terminals \Gamma = \{S, A, B, C\}. In particular, we have two production rules with S on the left hand side: S \to A and S \to B. \begin{align*} S &\to A \mid B \\ A &\to 0A \mid 0C \\ B &\to B1 \mid C1 \\ C &\to \varepsilon \mid 0C1 \end{align*}

We apply a production rule to a string in (\Sigma \cup \Gamma)^* by replacing any one instance of the non-terminal of the left of the rule with the string on its right. Again, each alternative between the | bars on a single line above is a separate production rule; we get to choose which one we’re going to apply and which copy of the non-terminal we’re going to replace.

Formally, for any x,y,z \in (\Sigma \cup \Gamma)^* and non-terminal A \in \Gamma, we apply production rule A \to y to the string xAz to get the string xyz. We denote the application by xAz \leadsto xyz.

For example, 00C1BAC0 \leadsto 000C11BAC0 when we apply the rule C \to 0C1 to the first C in the string on the left. Using the same rule but the other instance of C, we could also say 00C1BAC0 \leadsto 00C1BA0C10.

We say z derives from x, written x \leadsto^* z if x transforms into z via a finite sequence of production rules (a derivation). Each string (and in particular, each non-terminal) w has its own language L(w) := \{x \in \Sigma^* \mid w \leadsto^* x\} of strings that derive from w.1

Finally, the language L(G) generated by a context-free grammar G = (\Sigma, \Gamma, R, S) is the language L(S) of its starting non-terminal, and a language is called context-free if it is generated by some context-free grammar.

1

We sometimes also say each non-terminal A \in \Gamma generates the language L(A).

Basic facts

I’m going to give you just a few facts about CFGs context-free languages before we try designing some of our own.
TODO: Write up a quick proof for more of these even if they’re not presented in lecture.

Theorem: Every regular language is context free.

Jeff’s book contains two proofs. One converts an arbitrary regular expression into a CFG. The other converts an arbitrary DFA into a CFG.

Theorem: There are context-free languages that are not regular.

Proof: Consider the nonregular language \{0^n 1^n \mid n \geq 0\}.
It is generated by the following CFG: S \to \varepsilon \mid 0 S 1

Theorem: Not all languages are context-free.

In short, the set of CFGs is countably infinite, but the set of languages is not.

However, we do know many specific languages that are not context-free such \{0^n 1^n 0^n \mid n \geq 0\} and \{ww \mid w \in \{0,1\}^*\}. My own intuition is that adding recursion lets us count, but the “count” is heavily tied to recursion. As soon as we start “popping from the stack” to use the knowledge of how high we counted, it’s gone forever. The standard model of push down automata (not taught in this section) makes the intuition more explicit.

Another intuition is that we can share information such as number of 0s and 1s across a string, but we can only pair things using the information (leading to \{0^n 1^n 0^n \mid n \geq 0\} not being context-free) and the information sharing pairs cannot “cross” (leading to \{ww \mid w \in \{0, 1\}^*\} not being context-free.) We will not be doing any real proofs that certain languages are not context-free in this course. In particular, the technique used is quite a bit nastier than the fooling sets we used for nonregular languages, and the technique isn’t as powerful.

So, to emphasize, the set of regular languages is a proper subset of the set of context-free languages, and the set of context-free languages is itself a proper subset of the set of all languages.

Finally, context-free languages are closed under union, concatenation, and Kleene closure, just like in the definition of regular languages. However, context-free are not generally closed under complement or intersection! (See Problem 10 on tomorrow’s lab for an example of a language L that is not context free even though \bar{L} is context-free.)

Designing context-free grammars

Original example grammar

I want to start by emphasizing something that I don’t think I appreciated when I took CS 373 273 back in undergrad. Each string w, and in particular, each non-terminal A has its own language L(A), and in order to both understand and to properly explain grammar, you have to understand what these individual languages are.

It may help to think of a non-terminal as a procedure that prints strings. Once you know what a procedure does (not how it does so), you can better understand how other procedures that depend upon it work.

Recall our example grammar from earlier: \begin{align*} S &\to A \mid B \\ A &\to 0A \mid 0C \\ B &\to B1 \mid C1 \\ C &\to \varepsilon \mid 0C1 \end{align*}

I don’t think it’s obvious what the language of this grammar is, but maybe we can make sense of it by going one non-terminal at a time.

Let’s start with C, because it doesn’t rely on the other non-terminals. C is either empty, or it keeps “pushing” out 0s to the left and 1s to the right of middle of the string in equal number. Oh wait, we already saw this one in the proof above. L(C) = \{0^n 1^n \mid n \geq 0\}.

B makes one or more 1s to the right of what is eventually a C, deriving a member of the set \{C1^k \mid k > 0\}. Oh, but those will then derive \{0^m1^m 1^k \mid m \geq 0, k > 0\} = \{0^m 1^n \mid n > m\}. Similarly, L(A) = \{0^m 1^n \mid m > n\}.

Finally, S derives either A or B, so L(G) = L(S) = \{0^m 1^n \mid m \neq n\}.

When you describe CFGs on your homework, you must include self-contained descriptions of the set of strings generated by each nonterminal as part of your justification. This part of the justification should not refer to the overall string you’re trying to build using or how the nonterminals build it; only give what each nonterminal generates.

Giving simple languages described using set-builder notation is your safest bet. You might not have to say more if its clear enough how things fit together, or maybe you will. As always, see the solved problem 5 in the homework or the many lab problem solutions for examples of what we’re looking for.

Balanced parentheses

Let’s go back to our other motivating example. Can we generate the language of balanced parentheses (with nothing else going on)? There’s essentially three possibilities for a string of balanced parentheses.

In other words, we just need one non-terminal S with production rule S \to \varepsilon \mid SS \mid (S)

That grammar is perfectly acceptable for our goals in this course. However, it does have an issue for practical use of context-free grammars. It’s ambiguous, meaning at least one string in L(S) has multiple derivations (and not just out of order but with particular non-terminals being replaced using different production rules.) For example, the string (()()()) could be derived as follows: \begin{align*} S &\leadsto ( S ) \\ &\leadsto ( S S ) \\ &\leadsto (( S ) S ) \\ &\leadsto (() S ) \\ &\leadsto^* (()()()) \end{align*}

Or, it could be derived as follows here: \begin{align*} S &\leadsto ( S ) \\ &\leadsto ( S S ) \\ &\leadsto ( S ( S )) \\ &\leadsto ( S ()) \\ &\leadsto^* (()()()) \end{align*}

Ambiguity is bad for some applications such as parsing programs, because it could lead to a program evaluating expressions in a nondeterministic order.

Sometimes, a language is inherently ambiguous, meaning every context-free grammar is ambiguous, but not in this case. We could instead use the following nonambiguous grammar: S \to \varepsilon \mid (S) S

We do not need nonambiguous grammars for homework or exam solutions. Really, it’s just a bit of extra info that you might find useful outside this course.

Lots in the middle

Let’s look at one more example, strings over \{0, 1, 2\} of the form \{0^i 1^j 2^k \mid j > i + k\}. The huge number of 1s and the fact that we’re not trying to relate i and k directly will somehow let us avoid the intuitive issues that make a language not context-free.

Strings of this form can be described as, “an equal number of 0s and then 1s, followed by at least one 1, followed by an equal number of 1s and then 2s.” Let’s handle each piece by itself.

We’ll make a non-terminal A where L(A) = \{0^i 1^i \mid i \geq 0\}. As we’ve seen, that language can be derived using the pair of production rules A \to \varepsilon \mid 0A1.

We’ll make a non-terminal B where L(B) = \{1^j \mid j \geq 1\}. We’ll use the pair of production rules B \to 1 \mid 1B.

Finally, we’ll make a non-terminal C where L(C) = \{1^k 2^k \mid k \geq 0\}. Basically the same as before: C \to \varepsilon \mid 1C2

We finish by putting the pieces together: \begin{align*} S &\to A B C \\ A &\to \varepsilon \mid 0A1 \\ B &\to 1 \mid 1B \\ C &\to \varepsilon \mid 1C2 \end{align*}