Now we come to our next notion of computation beyond the regular languages and their associated models of computation, regexps nfas and dfas: the context free languages. Our motivating example is going to be the language we’ve seen repeatedly at this point, . We showed last time there was no way to make a DFA that decides this language.
Again, we’ll define our set of languages in terms of some model of computation. To this point, we introduce context free grammars (CFGs). A context free grammar is like a regular expression but much more powerful. The basic model of computation is the same: we have a set of symbols and rules to expand them. What’s different about CFGs over RegExps is that RegExps have a pre-defined set of rules for their expansion, meanwhile part of the definition of a CFG is the set of rules for expansion of symbols.
To whit, the CFG that matches our troublesome language is
So, for example, we can expand to get the string “00001111” by the sequence of expansions . Let’s define these CFGs a bit more formally.
A context free grammar is:
- A finite set of variables
- An alphabet , where and are disjoint. These are the “terminals” of the CFG.
- A finite set of rules , where a “rule” is a pair of a variable and a sequence of terminals and variables.
- A distinguished variable that’s the start variable
The set of strings that are generated by all the expansions of the grammar is the language described by the grammar. Again, it’s a finite computable process because since there are a finite number of rules and any string we are testing against has a finite length we can simply brute force check through all the expansions of the grammar that are the length of the target string.
We can do a number of other things with CFGs. For example, we could have a CFG for palindromes over an alphabet.
There’s one special form for CFGs that we should note specifically, which is Chomsky Normal Form. A CFG is in Chomsky Normal Form whenever it has the following properties
- Every expansion of a variable is either to exactly two variables or a single terminal, i.e. is of the form or
- No variable except the start variable can expand to
- No variable can expand to the start variable
This means that Chomsky Normal Form CFGs have a very simple inductive structure that we can take advantage of for proofs. What’s particularly useful is that, as we’ll show, all CFGs have an equivalent CFG in Chomsky Normal Form that generates the same language.
Now we make this construction clear in steps:
- We first introduce a new fresh start variable, , and have it expand to the old start variable
- The second step is that remove all rules of the form . This is a recursive process where we pick a variable that has an expansion and then we remove that rule and modify the rest of the expansions to account for the fact that can expand to nothing. We do this by taking every rule that contains an on the right hand side, i.e. something like , and replace it with a rule that has the removed, i.e. . Now, if the rule is then we replace it with . Wait, aren’t we removing the transitions? Yes, and so we iterate this process until all rules that have an on the rhs other than the start variable are eliminated. We are, essentially, propagating up the use of to the top of the derivation tree.
- Next, we replace all rules of the form by inlining the possible expansions of so that if we had and then we replace with . Note that in this step we don’t remove expansions from
- Now, finally, we take care of rules where a variable expands to more than two variables, more than one terminal, or a mixture of variables and terminals. If we have an expansion such as we replace the 0 with a new variable and a single expansion, i.e. will become and . If we have an expansion that has more than two variables, such as then we add a new variable that expands into the sequence piecewise, i.e. the rule becomes where . Note that there’s some freedom here but that no matter how you choose the steps involved you’ll get an equivalent grammar in Chomsky Normal Form
It’s probably a good time for an example, so let’s consider our language above for
Following step 1 of the above process, we get a new start symbol that must expand to so the grammar becomes
now, we eliminate the transitions.
You can see that everywhere there was an on the rhs, we’ve added a new rule that has the removed. Now the only place shows up is in an expansion of the start variable, which is allowed in Chomsky Normal Form.
Next, we eliminate unary transitions so now we have
Yes, this step has created a lot of redundancy in the rules. Chomsky Normal Form is useful for its simple inductive structure, but the price of simplicity is that we can no longer represent things as compactly as we’d like.
Finally, we put all the remaining rules in the proper form. First, we’ll clean up the terminals and then make the rest of rules only expand to two variables.
and after the final bit of cleanup
and our grammar is now in Chomsky Normal Form. Wow, umm, that’s a lot uglier and harder to read now isn’t it? Moving on!
So when dealing with the regular languages, we had regular expressions which had an interpretation as DFAs/NFAs. Now if CFGs play the role of regexps for the context-free languages, then what plays the role of the NFA? Let’s think for a moment about why we couldn’t build an NFA for that pesky language . We didn’t have any notion of “memory” for our NFA, there was no way to keep count of how many 0s we’d already seen so we’d know to only accept an equal number of 1s.
That being said, if we had something that was an awful lot like an NFA yet had a notion of memory then maybe that would solve the problem. That’s exactly what we’re going to introduce: Pushdown automata (PDAs). We’ll get to those next time.