In this section we deal with the pushdown automata and the class of languages — the contextfree languages — accepted by them.
As we have been seen in Section 1.1, a contextfree grammar is one with the productions of the form , , . The production is also permitted if does not appear in right hand side of any productions. Language is the contextfree language generated by grammar .
We have been seen that finite automata accept the class of regular languages. Now we get to know a new kind of automata, the socalled pushdown automata, which accept contextfree languages. The pushdown automata differ from finite automata mainly in that to have the possibility to change states without reading any input symbol (i.e. to read the empty symbol) and possess a stack memory, which uses the socalled stack symbols (See Fig. 1.31).
The pushdown automaton get a word as input, start to function from an initial state having in the stack a special symbol, the initial stack symbol. While working, the pushdown automaton change its state based on current state, next input symbol (or empty word) and stack top symbol and replace the top symbol in the stack with a (possibly empty) word.
There are two type of acceptances. The pushdown automaton accepts a word by final state when after reading it the automaton enter a final state. The pushdown automaton accepts a word by empty stack when after reading it the automaton empties its stack. We show that these two acceptances are equivalent.
Definition 1.21 A nondeterministic pushdown automaton is a system
where
is the finite, nonempty set of states
is the input alphabet,
is the stack alphabet,
is the set of transitions or edges,
is the initial state,
is the start symbol of stack,
is the set of final states.
A transition means that if pushdown automaton is in state , reads from the input tape letter (instead of input letter we can also consider the empty word ), and the top symbol in the stack is , then the pushdown automaton enters state and replaces in the stack by word . Writing word in the stack is made by natural order (letters of word will be put in the stack letter by letter from left to right). Instead of writing transition we will use a more suggestive notation .
Here, as in the case of finite automata, we can define a transition function
which associate to current state, input letter and top letter in stack pairs of the form , where is the word written in stack and the new state.
Because the pushdown automaton is nondeterministic, we will have for the transition function
(if the pushdown automaton reads an input letter and moves to right), or
(without move on the input tape).
A pushdown automaton is deterministic, if for any and we have
, and
if , then , .
We can associate to any pushdown automaton a transition table, exactly as in the case of finite automata. The rows of this table are indexed by elements of , the columns by elements from and (to each and will correspond a column). At intersection of row corresponding to state and column corresponding to and we will have pairs if . The transition graph, in which the label of edge will be corresponding to transition , can be also defined.
Example 1.25 . Elements of are:
The transition function:
The transition table:
Because for the transition function every set which is not empty contains only one element (e.g. ), in the above table each cell contains only one element, and the set notation is not used. Generally, if a set has more than one element, then its elements are written one under other. The transition graph of this pushdown automaton is in Fig. 1.32.
The current state, the unread part of the input word and the content of stack constitutes a configuration of the pushdown automaton, i.e. for each , and the triplet can be a configuration. If and , then the pushdown automaton can change its configuration in two ways:
,
if
,
if .
The reflexive and transitive closure of the relation will be denoted by . Instead of using , sometimes is considered.
How does work such a pushdown automaton? Getting started with the initial configuration we will consider all possible next configurations, and after this the next configurations to these next configurations, and so on, until it is possible.
Definition 1.22 Pushdown automaton accepts (recognizes) word by final state if there exist a sequence of configurations of for which the following are true:
the first element of the sequence is ,
there is a going from each element of the sequence to the next element, excepting the case when the sequence has only one element,
the last element of the sequence is , where and .
Therefore pushdown automaton accepts word by final state, if and only if for some and . The set of words accepted by final state by pushdown automaton will be called the language accepted by by final state and will be denoted by .
Definition 1.23 Pushdown automaton accepts (recognizes) word by empty stack if there exist a sequence of configurations of for which the following are true:
the first element of the sequence is ,
there is a going from each element of the sequence to the next element,
the last element of the sequence is and is an arbitrary state.
Therefore pushdown automaton accepts a word by empty stack if for some . The set of words accepted by empty stack by pushdown automaton will be called the language accepted by empty stack by and will be denoted by .
Example 1.26 Pushdown automaton of Example 1.25 accepts the language by final state. Consider the derivation for words and .
Word is accepted by the considered pushdown automaton because
and because is a final state the pushdown automaton accepts this word. But the stack being empty, it accepts this word also by empty stack.
Because the initial state is also a final state, the empty word is accepted by final state, but not by empty stack.
To show that word is not accepted, we need to study all possibilities. It is easy to see that in our case there is only a single possibility:
, but there is no further going, so word is not accepted.
Example 1.27 The transition table of the pushdown automaton is:
The corresponding transition graph can be seen in Fig. 1.33. Pushdown automaton accepts the language . Because is nemdeterministic, all the configurations obtained from the initial configuration can be illustrated by a computation tree. For example the computation tree associated to the initial configuration can be seen in Fig. 1.34. From this computation tree we can observe that, because is a leaf of the tree, pushdown automaton accepts word 1001 by empty stack. The computation tree in Fig. 1.35 shows that pushdown automaton does not accept word , because the configurations in leaves can not be continued and none of them has the form .
Figure 1.35. Computation tree to show that the pushdown automaton in Example 1.27 does not accept word .
Theorem 1.24 A language is accepted by a nondeterministic pushdown automaton by empty stack if and only if it can be accepted by a nondeterministic pushdown automaton by final state.
be the pushdown automaton which accepts by empty stack language . Define pushdown automaton , where and
.
Working of : Pushdown automaton with an move first goes in the initial state of , writing (the initial stack symbol of ) in the stack (beside ). After this it is working as . If for a given word empties its stack, then still has in the stack, which can be deleted by using an move, while a final state will be reached. can reach a final state only if has emptied the stack.
b) Let be a pushdown automaton, which accepts language by final state. Define pushdown automaton , where , and
.
Working : Pushdown automaton with an move writes in the stack beside the initial stack symbol of , then works as , i.e reaches a final state for each accepted word. After this empties the stack by an move. can empty the stack only if goes in a final state.
The next two theorems prove that the class of languages accepted by nondeterministic pushdown automata is just the set of contextfree languages.
Theorem 1.25 If is a contextfree grammar, then there exists such a nondeterministic pushdown automaton which accepts by empty stack, i.e. .
We outline the proof only. Let be a contextfree grammar. Define pushdown automaton , where , and the set of transitions is:
If there is in the set of productions of a production of type , then let put in the transition ,
For any letter let put in the transition . If there is a production in , the pushdown automaton put in the stack the mirror of with an move. If the input letter coincides with that in the top of the stack, then the automaton deletes it from the stack. If in the top of the stack there is a nonterminal , then the mirror of righthand side of a production which has in its lefthand side will be put in the stack. If after reading all letters of the input word, the stack will be empty, then the pushdown automaton recognized the input word.
The following algorithm builds for a contextfree grammar the pushdown automaton , which accepts by empty stack the language generated by .
FromCfgtoPushdownAutomaton(
)
1FOR
all productionDO
put in the transition 2FOR
all terminalDO
put in the transition 3RETURN
If has productions and terminals, then the number of step of the algorithm is .
Example 1.28 Let . Then , with the following transition table.
Let us see how pushdown automaton accepts word , which in grammar can be derived in the following way:
where productions and were used. Word is accepted by empty stack (see Fig. 1.36).
Theorem 1.26 For a nondeterministic pushdown automaton there exists always a contextfree grammar such that accepts language by empty stack, i.e. .
Instead of a proof we will give a method to obtain grammar . Let be the nondeterministic pushdown automaton in question.
Then , where
and .
Productions in will be obtained as follows.
For all state put in production .
If , where , () and , put in for all possible states productions
.
If , where , and , put in production
.
The contextfree grammar defined by this is an extended one, to which an equivalent contextfree language can be associated. The proof of the theorem is based on the fact that to every sequence of configurations, by which the pushdown automaton accepts a word, we can associate a derivation in grammar . This derivation generates just the word in question, because of productions of the form , which were defined for all possible states . In Example 1.27 we show how can be associated a derivation to a sequence of configurations. The pushdown automaton defined in the example recognizes word 00 by the sequence of configurations
,
which sequence is based on the transitions
,
,
.
To these transitions, by the definition of grammar , the following productions can be associated
(1) for all states ,
(2) ,
(3) .
Furthermore, for each state productions were defined.
By the existence of production there exists the derivation , where can be chosen arbitrarily. Let choose in above production (1) state to be equal to . Then there exists also the derivation
,
where can be chosen arbitrarily. If , then the derivation
will result. Now let equal to , then
,
which proves that word 00 can be derived used the above grammar.
The next algorithm builds for a pushdown automaton a contextfree grammar , which generates the language accepted by pushdown automaton by empty stack.
FromPushdownAutomatontoCfGrammar(
)
1FOR
all 2DO
put in production 3FOR
all , (), 4DO
FOR
all states 5DO
put in productions 6FOR
All , 7DO
put in production
If the automaton has states and productions, then the above algorithm executes at most steps, so in worst case the number of steps is . Finally, without proof, we mention that the class of languages accepted by deterministic pushdown automata is a proper subset of the class of languages accepted by nondeterministic pushdown automata. This points to the fact that pushdown automata behave differently as finite automata.
Example 1.29 As an example, consider pushdown automaton from the Example 1.28: . Grammar is:
where for all instead of we shortly used . The transitions:
Based on these, the following productions are defined:
.
It is easy to see that can be eliminated, and the productions will be:
,
,
, ,
and these productions can be replaced:
,
.
Consider contextfree grammar . A derivation tree of is a finite, ordered, labelled tree, which root is labelled by the the start symbol , every interior vertex is labelled by a nonterminal and every leaf by a terminal. If an interior vertex labelled by a nonterminal has descendents, then in there exists a production such that the descendents are labelled by letters , , . The result of a derivation tree is a word over , which can be obtained by reading the labels of the leaves from left to right. Derivation tree is also called syntax tree.
Consider the contextfree grammar . It generates language . Derivation of word is:
In Fig. 1.37 this derivation can be seen, which result is .
To every derivation we can associate a syntax tree. Conversely, to any syntax tree more than one derivation can be associated. For example to syntax tree in Fig. 1.37 the derivation
also can be associated.
Definition 1.27 Derivation is a leftmost derivation, if for all there exist words , and productions , for which we have
Consider grammar:
.
In this grammar word has two different leftmost derivations:
,
.
Definition 1.28 A contextfree grammar is ambiguous if in there exists a word with more than one leftmost derivation. Otherwise is unambiguous.
The above grammar is ambiguous, because word has two different leftmost derivations. A language can be generated by more than one grammar, and between them can exist ambiguous and unambiguous too. A contextfree language is inherently ambiguous, if there is no unambiguous grammar which generates it.
Example 1.30 Examine the following two grammars.
Grammar is ambiguous because
and
.
Grammar is unambiguous.
Can be proved that .
Like for regular languages there exists a pumping lemma also for contextfree languages.
Theorem 1.29 (pumping lemma) For any contextfree language there exists a natural number (which depends only on ), such that every word of the language longer than can be written in the form and the following are true:
(1) ,
(2) ,
(3) ,
(4) is also in for all .
Proof. Let be a grammar without unit productions, which generates language . Let be the number of nonterminals, and let be the maximum of lengths of righthand sides of productions, i.e. . Let and , such that . Then there exists a derivation tree with the result . Let be the height of (the maximum of path lengths from root to leaves). Because in all interior vertices have at most descendents, has at most leaves, i.e. . On the other hand, because of , we get that . From this follows that in derivation tree there is a path from root to a leave in which there are more than vertices. Consider such a path. Because in the number of nonterminals is and on this path vertices different from the leaf are labelled with nonterminals, by the pigeonhole principle, it must be a nonterminal on this path which occurs at least twice.
Let us denote by the nonterminal being the first on this path from root to the leaf which firstly repeat. Denote by the subtree, which root is this occurrence of . Similarly, denote by the subtree, which root is the second occurrence of on this path. Let be the result of the tree . Then the result of is in form , while of in . Derivation tree with this decomposition of can be seen in Fig. 1.38. We show that this decomposition of satisfies conditions (1)–(4) of lemma. Because in there are no productions (except maybe the case ), we have . Furthermore, because each interior vertex of the derivation tree has at least two descendents (namely there are no unit productions), also the root of has, hence . Because is the first repeated nonterminal on this path, the height of is at most , and from this results.
After eliminating from all vertices of excepting the root, the result of obtained tree is , i.e. .
Similarly, after eliminating we get , and finally because of the definition of we get Then . Therefore and for all . Therefore, for all we have , i.e. for all .
Now we present two consequences of the lemma.
Proof. This consequence states that there exists a contextsensitive language which is not contextfree. To prove this it is sufficient to find a contextsensitive language for which the lemma is not true. Let this language be .
To show that this language is contextsensitive it is enough to give a convenient grammar. In Example 1.2 both grammars are extended contextsensitive, and we know that to each extended grammar of type an equivalent grammar of the same type can be associated.
Let be the natural number associated to by lemma, and consider the word . Because of , if is contextfree can be decomposed in such that conditions (1)–(4) are true. We show that this leads us to a contradiction.
Firstly, we will show that word and can contain only one type of letters. Indeed if either or contain more than one type of letters, then in word the order of the letters will be not the order , so , which contradicts condition (4) of lemma.
If both and contain at most one type of letters, then in word the number of different letters will be not the same, so . This also contradicts condition (4) in lemma. Therefore is not contextfree.
Corollary 1.31 The class of contextfree languages is not closed under the intersection.
Proof. We give two contextfree languages which intersection is not contextfree. Let , and
where :
,
,
,
and , where :
,
,
.
Languages and are contextfree. But
is not contextfree (see the proof of the Consequence 1.30).
In the case of arbitrary grammars the normal form was defined (see Section 1.1) as grammars with no terminals in the lefthand side of productions. The normal form in the case of the contextfree languages will contains some restrictions on the righthand sides of productions. Two normal forms (Chomsky and Greibach) will be discussed.
Definition 1.32 A contextfree grammar is in Chomsky normal form, if all productions have form or , where , .
Example 1.31 Grammar is in Chomsky normal form and .
To each free contextfree language can be associated an equivalent grammar is Chomsky normal form. The next algorithm transforms an free contextfree grammar in grammar which is in Chomsky normal form.
ChomskyNormalForm(
)
1 2 eliminate unit productions, and let the new set of productions (see algorithmELIMINATEUNITPRODUCTIONS
in Section 1.1) 3 in replace in each production with at least two letters in righthand side all terminals by a new nonterminal , and add this nonterminal to and add production to 4 replace all productions , where and , by the following: , , , , where are new nonterminals, and add them to 5RETURN
Example 1.32 Let . It is easy to see that . Steps of transformation to Chomsky normal form are the following:
Step 1:
Step 2: After eliminating the unit production the productions are:
,
.
Step 3: We introduce three new nonterminals because of the three terminals in productions. Let these be . Then the production are:
,
,
,
.
Step 4: Only one new nonterminal (let this ) must be introduced because of a single production with three letters in the righthand side. Therefore , and the productions in are:
,
,
,
,
.
All these productions are in required form.
Definition 1.33 A contextfree grammar is in Greibach normal form if all production are in the form , where , , .
Example 1.33 Grammar is in Greibach normal form and .
To each free contextfree grammar an equivalent grammar in Greibach normal form can be given. We give and algorithm which transforms a contextfree grammar in Chomsky normal form in a grammar in Greibach normal form.
First, we give an order of the nonterminals: , where is the start symbol. The algorithm will use the notations , .
GreibachNormalForm(
)
1 2 3FOR
TO
Case 4DO
FOR
TO
5DO
for all productions and (where has no as first letter) in productions , delete from productions 6IF
there is a production Case 7THEN
put in the new nonterminal , for all productions put in productions and , delete from production ,empty≥ for all production (where is not the first letter of ) put in production 8FOR
DOWNTO
Case 9DO
FOR
TO
10DO
for all productions and put in production and delete from productions , 11FOR
TO
Case 12DO
FOR
TO
13DO
for all productions and put in production and delete from productions 14RETURN
The algorithm first transform productions of the form such that or , where this latter is in Greibach normal form. After this, introducing a new nonterminal, eliminate productions , and using substitutions all production of the form and will be transformed in Greibach normal form.
Example 1.34 Transform productions in Chomsky normal form
in Greibach normal form.
Steps of the algorithm:
3–5: Production must be transformed. For this production is appropriate. Put in the set of productions and eliminate .
The productions will be:
6–7: Elimination of production will be made using productions:
Then, after steps 6–7. the productions will be:
8–10: We make substitutions in productions with in lefthand side. The results is:
11–13: Similarly with productions with in lefthand side:
After the elimination in steps 8–13 of productions in which substitutions were made, the following productions, which are now in Greibach normal form, result:
can be generated by grammar
First, will eliminate the single unit production, and after this we will give an equivalent grammar in Chomsky normal form, which will be transformed in Greibach normal form.
Productions after the elimination of production :
.
We introduce productions , and replace terminals by the corresponding nonterminals:
,
,
.
After introducing two new nonterminals (, ):
,
,
,
,
.
This is now in Chomsky normal form. Replace the nonterminals to be letters as in the algorithm. Then, after applying the replacements
replaced by , replaced by , replaced by , replaced by , replaced by , replaced by , replaced by ,
our grammar will have the productions:
,
,
,
,
.
In steps 3–5 of the algorithm the new productions will occur:
then
, then
.
Therefore
,
,
,
.
Steps 6–7 will be skipped, because we have no leftrecursive productions. In steps 8–10 after the appropriate substitutions we have:
,
,
,
,
,
.
Exercises
1.31 Give pushdown automata to accept the following languages:
,
,
.
1.32 Give a contextfree grammar to generate language , and transform it in Chomsky and Greibach normal forms. Give a pushdown automaton which accepts .
1.33 What languages are generated by the following contextfree grammars?
.
1.34 Give a contextfree grammar to generate words with an equal number of letters and .
1.35 Prove, using the pumping lemma, that a language whose words contains an equal number of letters , and can not be contextfree.
1.36 Let the grammar , where
,
,
,
Show that word if a then if a then c else c has two different leftmost derivations.
1.37 Prove that if is contextfree, then is also contextfree.
PROBLEMS

11
Linear grammars
A grammar which has productions only in the form or , where , is called a linear grammar. If in a linear grammar all production are of the form or , then it is called a leftlinear grammar. Prove that the language generated by a leftlinear grammar is regular.
12
Operator grammars
An free contextfree grammar is called operator grammar if in the righthand side of productions there are no two successive nonterminals. Show that, for all free contextfree grammar an equivalent operator grammar can be built.
13
Complement of contextfree languages
Prove that the class of contextfree languages is not closed on complement.
CHAPTER NOTES

In the definition of finite automata instead of transition function we have used the transition graph, which in many cases help us to give simpler proofs.
There exist a lot of classical books on automata and formal languages. We mention from these the following: two books of Aho and Ullman [ 5 ], [ 6 ] in 1972 and 1973, book of Gécseg and Peák [ 87 ] in 1972, two books of Salomaa [ 221 ], [ 222 ] in 1969 and 1973, a book of Hopcroft and Ullman [ 118 ] in 1979, a book of Harrison [ 108 ] in 1978, a book of Manna [ 174 ], which in 1981 was published also in Hungarian. We notice also a book of Sipser [ 242 ] in 1997 and a monograph of Rozenberg and Salomaa [ 220 ]. In a book of Lothaire (common name of French authors) [ 166 ] on combinatorics of words we can read on other types of automata. Paper of Giammarresi and Montalbano [ 89 ] generalise the notion of finite automata. A new monograph is of Hopcroft, Motwani and Ullman [ 117 ]. In German we recommend the textbook of Asteroth and Baier [ 14 ]. The concise description of the transformation in Greibach normal form is based on this book.
A practical introduction to formal languages is written by Webber [ 270 ].
Other books in English: [ 32 ], [ 40 ], [ 68 ], [ 142 ], [ 149 ], [ 159 ], [ 164 ], [ 165 ], [ 177 ], [ 185 ], [ 238 ], [ 240 ], [ 251 ], [ 252 ].
At the end of the next chapter on compilers another books on the subject are mentioned.