PDAs and context-free grammars#
Moving on from DFAs, NFAs and regular languages, we next consider more powerful models of computation, namely pushdown automata (PDAs) and context-free grammars (CFGs). These turn out to be analogous to finite-state automata and regular languages, but are more powerful. In particular, we will show that CFGs and PDAs are equivalent and that they are strict supersets of regular languages and NFAs.
Context-free grammars#
A CFG consists of variables and terminal symbols, as well as rules which expand these variables into strings of other variables and terminal symbols.
Definition 9 (Context-free grammar)
A context-free grammar (CGG) is a 4-tuple
is a finite set called the variables, is a finite set that is disjoint from , called the terminals, is a finite set of rules, with each rule being a pair consisting of a variable and a string of variables and terminals, is the start variable.
We now introduce some terminology on CFGs. We say that a string yields another if the latter can be obtained by applying a rule of a CFG onto the former. Similarly, we say that a string derives another if the latter can be obtained by applying a finite number of rules to it.
Definition 10 (Yields, derives)
If
Similarly to DFAs and NFAs, we define the language of a CFG to be the set of strings it can represent, i.e. the set of strings that can be derived from it.
Definition 11 (Context-free language)
We define the language of a CFG
We can now look at a couple of examples of CFGs and strings that these generate.
We can visualise the derivation of a string in a language using a parse tree, where each node is a variable or terminal symbol and each edge corresponds to part of a substitution rule.
First is the following example of a CFG which generates all strings of the form
Example 6 (Example CFG)
Consider the CFG
Below is an example of a derivation of the string

We also have the following example CFG which generates valid mathematical expressions involving sums and multiplications. CFGs similar to this can be used to define parsers for programming languages.
Example 7 (Example CFG for mathematical expressions)
Consider the CFG
Below is an example of a derivation of the string

Sometimes, a string in a CFL can be derived in more than one way (even if we account for applications of the same rules in different orders). In such cases, the language is ambiguous in the sense that there may be more than one parse tree that correspond to the same given string. The following definitions formalise this notion.
Definition 12 (Leftmost derivation)
We call a derivation of a string in a CFG a leftmost derivation if at every step of the derivation the leftmost variable is the one that is replaced.
This idea allows us to succinctly define ambiguous languages.
Definition 13 (Ambiguity)
We say that a string
Some CFLs are inherently ambiguous, which means that they can be generated only by ambiguous grammars.
Chomsky normal form#
Definition 14 (Chomsky normal form)
A context-free grammar is in Chomsky normal form if every rule is of the form
where
Lemma 4 (CFLs generated by CFG in Chomsky normal form)
Any context-free language is generated by a context-free grammar in Chomsky normal form.
Proof: CFLs generated by CFG in Chomsky normal form
Let
Step 1:
First, define a new start variable
Step 2:
Second, we eliminate all
Step 3:
Third, we handle unit rules.
If there is a unit rule of the form
Step 4:
Last, we convert all remaining rulles in proper form.
We replace each rule
The grammar
Pushdown Automata#
Now we move to pushdown automata (PDA), which are another kind of computational model. PDAs are similar to NFAs in that they have a finite number of states and allow for nondeterminism. We will show that PDAs have the same expressive power as CFGs, in a somewhat analogous way that NFAs have the same power as regular expressions. It will turn out that PDAs are very useful in this sense because they provide another way to prove things about CFLs, in addition to CFGs. PDAs extend NFAs by introducing a stack of symbols, from which they can read symbols as well as add new ones or remove existing symbols. The stack itself can be of infinite length, which is what makes PDAs more powerful than NFAs.
Definition 15 (Pushdown automaton (PDA))
A pushdown automaton is a
is a finite set, the set of states, is a finite set, the input alphabet, is a finite set, the stack alphabet, is a function, the transition funciton, is the start state, is the set of accept states.
Crucially a PDA can only read, write or remove symbols at the top of the stack. Now we define what it means for a PDA to accept a string, which is analogous to an NFA accepting a string.
Definition 16 (PDA accepts)
A pushdown automaton
andFor
we have where with and
Context Free Pumping Lemma#
Theorem 6 (Pumping Lemma for CFLs)
For every CFL
for all , , .
Example 8 (A non-context-free language)
The language
Proof
Suppose
Lemma 5 (CFL not closed under intersection)
The class of context-free languages are not closed under intersection.
Proof
The languages