1.3. 1.3 Pushdown automata and context-free languages

In this section we deal with the pushdown automata and the class of languages — the context-free languages — accepted by them.

As we have been seen in Section 1.1, a context-free 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 context-free language generated by grammar .

1.3.1. 1.3.1 Pushdown automata

We have been seen that finite automata accept the class of regular languages. Now we get to know a new kind of automata, the so-called pushdown automata, which accept context-free 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 so-called stack symbols (See Fig. 1.31).

Figure 1.31.  Pushdown automaton.

Pushdown automaton.


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, non-empty 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.

Figure 1.32.  Example of pushdown automaton.

Example of pushdown automaton.

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:

Figure 1.33.  Transition graph of the Example 1.27

Transition graph of the Example 1.27


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.34.  Computation tree to show acceptance of the word Computation tree to show acceptance of the word 1001 (see Example 1.27). (see Example 1.27).

Computation tree to show acceptance of the word 1001 (see Example 1.27).

Figure 1.35.  Computation tree to show that the pushdown automaton in Example 1.27 does not accept word Computation tree to show that the pushdown automaton in Example 1.27 does not accept word 101 ..

Computation tree to show that the pushdown automaton in Example 1.27 does not accept word 101 .

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.

Proof. a) Let

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 context-free languages.

Theorem 1.25 If is a context-free grammar, then there exists such a nondeterministic pushdown automaton which accepts by empty stack, i.e. .

We outline the proof only. Let be a context-free 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 right-hand side of a production which has in its left-hand 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 context-free grammar the pushdown automaton , which accepts by empty stack the language generated by .

From-Cfg-to-Pushdown-Automaton( )

  1  
                        FOR
                      all production            
                     
                        DO
                      put in  the transition   2  
                        FOR
                      all terminal             
                     
                        DO
                      put in  the transition   3  
                        RETURN
                      
                       
                  

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).

Figure 1.36.  Recognising a word by empty stack (see Example 1.28).

Recognising a word by empty stack (see Example 1.28).

Theorem 1.26 For a nondeterministic pushdown automaton there exists always a context-free 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 context-free grammar defined by this is an extended one, to which an equivalent context-free 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 context-free grammar , which generates the language accepted by pushdown automaton by empty stack.

From-Pushdown-Automaton-to-Cf-Grammar( )

  1  
                        FOR
                      all    2    
                        DO
                      put in  production    3  
                        FOR
                      all        
                      
                     ,          (),   4       
                        DO
                      
                     
                        FOR
                      all states    5          
                        DO
                      put in  productions    6  
                        FOR
                      All        
                      
                     ,     7       
                        DO
                      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:

,

.

1.3.2. 1.3.2 Context-free languages

Consider context-free 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 context-free grammar . It generates language . Derivation of word is:

In Fig. 1.37 this derivation can be seen, which result is .

Figure 1.37.  Derivation (or syntax) tree of word Derivation (or syntax) tree of word aaaabb ..

Derivation (or syntax) tree of word aaaabb .


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 context-free 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 context-free 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 .

1.3.3. 1.3.3 Pumping lemma for context-free languages

Like for regular languages there exists a pumping lemma also for context-free languages.

Theorem 1.29 (pumping lemma) For any context-free 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 .

Figure 1.38.  Decomposition of tree in the proof of pumping lemma.

Decomposition of tree in the proof of pumping lemma.

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 right-hand 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.

Corollary 1.30 .

Proof. This consequence states that there exists a context-sensitive language which is not context-free. To prove this it is sufficient to find a context-sensitive language for which the lemma is not true. Let this language be .

To show that this language is context-sensitive it is enough to give a convenient grammar. In Example 1.2 both grammars are extended context-sensitive, 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 context-free 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 context-free.

Corollary 1.31 The class of context-free languages is not closed under the intersection.

Proof. We give two context-free languages which intersection is not context-free. Let , and

where :

,

,

,

and , where :

,

,

.

Languages and are context-free. But

is not context-free (see the proof of the Consequence 1.30).

1.3.4. 1.3.4 Normal forms of the context-free languages

In the case of arbitrary grammars the normal form was defined (see Section 1.1) as grammars with no terminals in the left-hand side of productions. The normal form in the case of the context-free languages will contains some restrictions on the right-hand sides of productions. Two normal forms (Chomsky and Greibach) will be discussed.

1.3.4.1.  Chomsky normal form

Definition 1.32 A context-free 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 context-free language can be associated an equivalent grammar is Chomsky normal form. The next algorithm transforms an -free context-free grammar in grammar which is in Chomsky normal form.

Chomsky-Normal-Form( )

  1     2  eliminate unit productions, and let  the new set of productions        (see algorithm 
                           ELIMINATE-UNIT-PRODUCTIONS
                         in Section 1.1)  3  in  replace in each production with at least two letters in right-hand 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   5  
                           RETURN
                         
                         
                     

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 right-hand side. Therefore , and the productions in are:

,

,

,

,

.

All these productions are in required form.

1.3.4.2.  Greibach normal form

Definition 1.33 A context-free 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 context-free grammar an equivalent grammar in Greibach normal form can be given. We give and algorithm which transforms a context-free 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 , .

Greibach-Normal-Form( )

  1     2     3  
                           FOR
                         
                         
                        
                           TO
                         
                              
                         Case    4    
                           DO
                         
                        
                           FOR
                         
                         
                        
                           TO
                         
                           5       
                           DO
                         for all productions  and  (where  has no                  as first letter) in  productions ,                delete from  productions   6    
                           IF
                         there is a production       
                         Case    7       
                           THEN
                         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   8  
                           FOR
                         
                         
                        
                           DOWNTO
                         
                              
                         Case    9    
                           DO
                         
                        
                           FOR
                         
                         
                        
                           TO
                         
                          10       
                           DO
                         for all productions  and                  put in  production  and                delete from  productions , 11  
                           FOR
                         
                         
                        
                           TO
                         
                              
                         Case   12    
                           DO
                         
                        
                           FOR
                         
                         
                        
                           TO
                         
                          13       
                           DO
                         for all productions  and                  put in  production  and                delete from  productions  14  
                           RETURN
                         
                         
                     

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 left-hand side. The results is:

11–13: Similarly with productions with in left-hand 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:

Example 1.35 Language

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 left-recursive productions. In steps 8–10 after the appropriate substitutions we have:

,

,

,

,

,

.

Exercises

1.3-1 Give pushdown automata to accept the following languages:

,

,

.

1.3-2 Give a context-free grammar to generate language , and transform it in Chomsky and Greibach normal forms. Give a pushdown automaton which accepts .

1.3-3 What languages are generated by the following context-free grammars?

.

1.3-4 Give a context-free grammar to generate words with an equal number of letters and .

1.3-5 Prove, using the pumping lemma, that a language whose words contains an equal number of letters , and can not be context-free.

1.3-6 Let the grammar , where

,

,

,

Show that word if a then if a then c else c has two different leftmost derivations.

1.3-7 Prove that if is context-free, then is also context-free.

  PROBLEMS  

1-1 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 left-linear grammar. Prove that the language generated by a left-linear grammar is regular.

1-2 Operator grammars

An -free context-free grammar is called operator grammar if in the right-hand side of productions there are no two successive nonterminals. Show that, for all -free context-free grammar an equivalent operator grammar can be built.

1-3 Complement of context-free languages

Prove that the class of context-free 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.