If are languages over we define the following operations

union

intersection

difference

complement

multiplication

power

if

iteration or star operation

mirror

We will use also the notation

The union, product and iteration are called regular operations.

Languages can be specified in several ways. For example a language can be specified using

1) the enumeration of its words,

2) a property, such that all words of the language have this property but other word have not,

3) a grammar.

Specifying languages by grammars.

Define the generative grammar or shortly the grammar.

Definition 1.1 A grammar is an ordered quadruple , where

is the alphabet of variables (or nonterminal symbols),

is the alphabet of terminal symbols, where ,

is a finite set, that is is the finite set of productions of the form , where and contains at least a nonterminal symbol,

is the start symbol.

Remarks. Instead of the notation sometimes is used.

In the production or word is called the left-hand side of the production while the right-hand side. If for a grammar there are more than one production with the same left-hand side, then these production

We define on the set the relation called direct derivation

In fact we replace in an appearance of the subword by and we get . Another notations for the same relation can be or .

If we want to emphasize the used grammar , then the notation can be replaced by . Relation is the reflexive and transitive closure of , while denotes its transitive closure. Relation is called a derivation.

From the definition of a reflexive and transitive relation we can deduce the following: , if there exist the words and . This can be written shortly If then . The same way we can define the relation except that always, so at least one direct derivation will de used.

Definition 1.2 The language generated by grammar is the set

So contains all words over the alphabet which can be derived from the start symbol using the productions from .

Example 1.1 Let where

It is easy to see than because

where up to the last but one replacement the first production () was used, while at the last replacement the production . This derivation can be written Therefore can be derived from for all and no other words can be derived from .

Definition 1.3 Two grammars and are equivalent, and this is denoted by if .

Example 1.2 The following two grammars are equivalent because both of them generate the language .

, where

,

where

First let us prove by mathematical induction that for If then

The inductive hypothesis is We use production , then times production , and then production , afterwards again times production . Therefore

If now we use production we get for , but by the production , so for any . We have to prove in addition that using the productions of the grammar we cannot derive only words of the form . It is easy to see that a successful derivation (which ends in a word containing only terminals) can be obtained only in the presented way.

Similarly for

Here orderly were used the productions ( times), , ( times), , ( times), , ( times). But So , . It is also easy to see than other words cannot be derived using grammar .

The grammars and are not equivalent because .

Theorem 1.4 Not all languages can be generated by grammars.

Proof. We encode grammars for the proof as words on the alphabet . For a given grammar let and The encoding is the following:

the code of is the code of is

In the code of the grammar the letters are separated by 000, the code of the arrow is 0000, and the productions are separated by 00000.

It is enough, of course, to encode the productions only. For example, consider the grammar

.

The code of is 10101, the code of is 1001001, the code of is 10011001. The code of the grammar is

From this encoding results that the grammars with terminal alphabet can be enumerated as and the set of these grammars is a denumerable infinite set.

Footnote Let us suppose that in the alphabet there is a linear order , let us say . The words which are codes of grammars can be enumerated by ordering them first after their lengths, and inside the equal length words, alphabetically, using the order of their letters. But we can use equally the lexicographic order, which means that ( is before ) if is a proper prefix of or there exists the decompositions and , where , , are subwords, and letters with .

Consider now the set of all languages over denoted by , that is . The set is denumerable because its words can be ordered. Let this order , where . We associate to each language an infinite binary sequence the following way:

It is easy to see that the set of all such binary sequences is not denumerable, because each sequence can be considered as a positive number less than 1 using its binary representation (The decimal point is considered to be before the first digit). Conversely, to each positive number less than 1 in binary representation a binary sequence can be associated. So, the cardinality of the set of infinite binary sequences is equal to cardinality of interval , which is of continuum power. Therefore the set is of continuum cardinality. Now to each grammar with terminal alphabet associate the corresponding generated language over . Since the cardinality of the set of grammars is denumerable, there will exist a language from , without associated grammar, a language which cannot be generated by a grammar.

Putting some restrictions on the form of productions, four type of grammars can be distinguished.

Definition 1.5 Define for a grammar the following four types.

A grammar is of type 0 (phrase-structure grammar) if there are no restrictions on productions.

A grammar is of type 1 (context-sensitive grammar) if all of its productions are of the form , where , , . A production of the form can also be accepted if the start symbol does not occur in the right-hand side of any production.

A grammar is of type 2 (context-free grammar) if all of its productions are of the form , where , . A production of the form can also be accepted if the start symbol does not occur in the right-hand side of any production.

A grammar is of type 3 (regular grammar) if its productions are of the form or , where and . A production of the form can also be accepted if the start symbol does not occur in the right-hand side of any production.

If a grammar is of type then language is also of type .

This classification was introduced by Noam Chomsky.

A language is of type () if there exists a grammar of type which generates the language , so .

Denote by () the class of the languages of type . Can be proved that

By the definition of different type of languages, the inclusions () are evident, but the strict inclusions () must be proved.

Example 1.3 We give an example for each type of context-sensitive, context-free and regular grammars.

Context-sensitive grammar. , where

Elements of are:

Language contains words of the form with and .

Context-free grammar. , where

Elements of are:

Language contains algebraic expressions which can be correctly built using letter , operators and and brackets.

Regular grammar. , where

Elements of are:

Language contains words over the alphabet with at least two letters at the beginning.

It is easy to prove that any finite language is regular. The productions will be done to generate all words of the language. For example, if is in the language, then we introduce the productions: , , , where is the start symbol of the language and are distinct nonterminals. We define such productions for all words of the language using different nonterminals for different words, excepting the start symbol . If the empty word is also an element of the language, then the production is also considered.

The empty set is also a regular language, because the regular grammar generates it.

  1  if the unit productions  and  are in  put also 
       the unit production  in  while  can be extended
  2  if the unit production  and the production  () are in  
       put also the production  in 
  3  let  be the set of productions of  except unit productions 
  4  RETURN  

Grammars in normal forms.

A grammar is to be said a grammar in normal form if its productions have no terminal symbols in the left-hand side.

We need the following notions. For alphabets and a homomorphism is a function for which . It is easy to see that for arbitrary value is uniquely determined by the restriction of on , because

If a homomorphism is a bijection then is an isomorphism.

Theorem 1.6 To any grammar an equivalent grammar in normal form can be associated.

Proof. Grammars of type 2 and 3 have in left-hand side of any productions only a nonterminal, so they are in normal form. The proof has to be done for grammars of type 0 and 1 only.

Let be the original grammar and we define the grammar in normal form as .

Let be those terminal symbols which occur in the left-hand side of productions. We introduce the new nonterminals . The following notation will be used: , , and .

Define the isomorphism , where

Define the set of production as

In this case if and only if From this the theorem immediately results because

Example 1.5 Let , where contains

In the left-hand side of productions the terminals occur, therefore consider the new nonterminals , and include in also the new productions , and .

Terminals will be replaced by nonterminals respectively, and we get the set as

Let us see what words can be generated by this grammars. It is easy to see that because

, so

We prove, using the mathematical induction, that for . For this is the case, as we have seen before. Continuing the derivation we get , and this is what we had to prove.

But So . These words can be generated also in .

In this subsection extended grammars of type 1, 2 and 3 will be presented.

Extended grammar of type 1. All productions are of the form , where , excepted possibly the production .

Extended grammar of type 2. All productions are of the form , where

Extended grammar of type 3. All productions are of the form or , where .

Theorem 1.7 To any extended grammar an equivalent grammar of the same type can be associated.

Proof. Denote by the extended grammar and by the corresponding equivalent grammar of the same type.

Type 1. Define the productions of grammar by rewriting the productions , where of the extended grammar in the form allowed in the case of grammar by the following way.

Let () be a production of , which is not in the required form. Add to the set of productions of the following productions, where are new nonterminals:

Furthermore, add to the set of productions of without any modification the productions of which are of permitted form, i.e. . Inclusion can be proved because each used production of in a derivation can be simulated by productions obtained from it. Furthermore, since the productions of can be used only in the prescribed order, we could not obtain other words, so also is true.

Type 2. Let . Productions of form have to be eliminated, only can remain, if doesn't occur in the right-hand side of productions. For this define the following sets:

Since for we have , and is a finite set, there must exists such a for which . Let us denote this set as . It is easy to see that a nonterminal is in if and only if . (In addition if and only if .)

We define the productions of starting from the productions of in the following way. For each production with of add to the set of productions of this one and all productions which can be obtained from it by eliminating from one or more nonterminals which are in , but only in the case when the right-hand side does not become .

It in not difficult to see that this grammar generates the same language as does, except the empty word . So, if then the proof is finished. But if , then there are two cases. If the start symbol does not occur in any right-hand side of productions, then by introducing the production , grammar will generate also the empty word. If occurs in a production in the right-hand side, then we introduce a new start symbol and the new productions and . Now the empty word can also be generated by grammar .

Type 3. First we use for the procedure defined for grammars of type 2 to eliminate productions of the form . From the obtained grammar we eliminate the unit productions using the algorithm ELIMINATE-UNIT-PRODUCTIONS.

In the obtained grammar for each production , where , add to the productions of also the followings

where are new nonterminals. It is easy to prove that grammar built in this way is equivalent to .

Example 1.6 Let be an extended grammar of type 1, where , and contains the following productions:

The only production which is not context-sensitive is . Using the method given in the proof, we introduce the productions:

Now the grammar is context-sensitive, where the elements of are

It can be proved that .

Example 1.7 Let be an extended grammar of type 2, where contains:

Then , , . The productions of the new grammar are:

The original grammar generates also the empty word and because occurs in the right-hand side of a production, a new start symbol and two new productions will be defined: . The context-free grammar equivalent to the original grammar is with the productions:

Both of these grammars generate language .

Example 1.8 Let be the extended grammar of type 3 under examination, where :

First, we eliminate production . Since , the productions will be

The latter production (which a unit production) can also be eliminated, by replacing it with . Productions and have to be transformed. Since, both productions have the same right-hand side, it is enough to introduce only one new nonterminal and to use the productions and instead of . Production will be replaced by . The new grammar is , where :

Can be proved that .

We will prove the following theorem, by which the Chomsky-classes of languages are closed under the regular operations, that is, the union and product of two languages of type is also of type , the iteration of a language of type is also of type ().

Theorem 1.8 The class () of languages is closed under the regular operations.

Proof. For the proof we will use extended grammars. Consider the extended grammars and of type each. We can suppose that .

Union. Let .

We will show that If then from the assumption that and are of type follows by definition that also is of type . If and one of the grammars generates the empty word, then we eliminate from the corresponding production (possibly the both) () and replace it by production .

Product. Let .

We will show that By definition, if then will be of the same type. If and there is production in but there is no production in then production will be replaced by . We will proceed the same way in the symmetrical case. If there is in production and in production then they will be replaced by .

In the case of regular grammars (), because is not a regular production, we need to use another grammar , where the difference between and lies in that instead of productions in the form in will exist production of the form .

Iteration. Let .

In the case of grammars of type 2 let . Then also is of type 2.

In the case of grammars of type 3, as in the case of product, we will change the productions, that is , where the difference between and lies in that for each will be replaced by , and the others will be not changed. Then also will be of type 3.

The productions given in the case of type 2 are not valid for , because when applying production we can get the derivations of type , , , where can be a left-hand side of a production. In this case, replacing by its right-hand side in derivation , we can generate a word which is not in the iterated language. To avoid such situations, first let us assume that the language is in normal form, i.e. the left-hand side of productions does not contain terminals (see Section 1.1), second we introduce a new nonterminal , so the set of nonterminals now is , and the productions are the following:

Now we can avoid situations in which the left-hand side of a production can extend over the limits of words in a derivation because of the iteration. The above derivations can be used only by beginning with and getting derivation . Here we can not replace unless the last symbol in is a terminal symbol, and only after using a production of the form .

It is easy to show that for each type.

Exercises

1.1-1 Give a grammar which generates language and determine its type.

1.1-2 Let be an extended context-free grammar, where ,

.

Give an equivalent context-free grammar.

1.1-3 Show that and are regular languages over arbitrary alphabet .

1.1-4 Give a grammar to generate language , where represents the number of 0's in word and the number of 1's.

1.1-5 Give a grammar to generate all natural numbers.

1.1-6 Give a grammar to generate the following languages, respectively:

,

,

,

.

1.1-7 Let be an extended grammar, where , and contains the productions:

Determine the type of this grammar. Give an equivalent, not extended grammar with the same type. What language it generates?

As follows we will show that any NFA can be transformed in an equivalent DFA.

Theorem 1.10 For any NFA one may construct an equivalent DFA.

Proof. Let be an NFA. Define a DFA , where

,

edges of are those triplets for which are not empty, and ,

,

.

We prove that .

a) First prove that . Let . Then there exists a walk

Using the transition function of NFA we construct the sets , . Then and since we get , so . Thus, there exists a walk

There are sets for which , and for we have , and

is a productive walk. Therefore . That is .

b) Now we show that . Let . Then there is a walk

Using the definition of we have , i.e. there exists , that is by the definitions of and there is such that . Similarly, there are the states such that , where , thus, there is a walk

so .

In constructing DFA we can use the corresponding transition function :

The empty set was excluded from the states, so we used here instead of .

Figure 1.5.  The equivalent DFA with NFA in Fig. 1.3.

Example 1.10 Apply Theorem 1.10 to transform NFA in Fig. 1.3. Introduce the following notation for the states of the DFA:

where is the initial state. Using the transition function we get the transition table:

This automaton contains many inaccessible states. By algorithm INACCESSIBLE-STATES we determine the accessible states of DFA:

.

Initial state is also a final state. States and are final states. States are inaccessible and can be removed from the DFA. The transition table of the resulted DFA is

The corresponding transition graph is in Fig. 1.5.

The algorithm given in Theorem 1.10 can be simplified. It is not necessary to consider all subset of the set of states of NFA. The states of DFA can be obtained successively. Begin with the state and determine the states for all . For the newly obtained states we determine the states accessible from them. This can be continued until no new states arise.

In our previous example is the initial state. From this we get

The transition table is

which is the same (excepted the notation) as before.

The next algorithm will construct for an NFA the transition table of the equivalent DFA , but without to determine the final states (which can easily be included). Value of ISIN() in the algorithm is true if state is already in and is false otherwise. Let be an ordered list of the letters of .

NFA-DFA(A)

  1   
  2   
  3          counts the rows. 
  4          counts the states. 
  5  REPEAT 
  6    FOR         counts the columns. 
  7       DO  
  8          IF  
  9             THEN IF ISIN() 
 10                THEN  
 11                ELSE  
 12                    
 13                    
 14                    
 15             ELSE  
 16     
 17  UNTIL  
 18  RETURN transition table  of  

Since loop rEPEAT is executed as many times as the number of states of new automaton, in worst case the running time can be exponential, because, if the number of states in NFA is , then DFA can have even states. (The number of subsets of a set of elements is , including the empty set.)

Theorem 1.10 will have it that to any NFA one may construct an equivalent DFA. Conversely, any DFA is also an NFA by definition. So, the nondeterministic finite automata accepts the same class of languages as the deterministic finite automata.

In this subsection we will use complete deterministic finite automata only. In this case has a single element. In formulae, sometimes, instead of set we will use its single element. We introduce for a set the function which give us the single element of set , so . Using walks which begin with the initial state and have the same label in two DFA's we can determine the equivalence of these DFA's. If only one of these walks ends in a final state, then they could not be equivalent.

Consider two DFA's over the same alphabet and . We are interested to determine if they are or not equivalent. We construct a table with elements of form , where and . Beginning with the second column of the table, we associate a column to each letter of the alphabet . If the first element of the th row is then at the cross of th row and the column associated to letter will be the pair .

In the first column of the first row we put and complete the first row using the above method. If in the first row in any column there occur a pair of states from which one is a final state and the other not then the algorithm ends, the two automata are not equivalent. If there is no such a pair of states, every new pair is written in the first column. The algorithm continues with the next unfilled row. If no new pair of states occurs in the table and for each pair both of states are final or both are not, then the algorithm ends and the two DFA are equivalent.

If , and then taking into account that in worst case loop rEPEAT is executed times, loop fOR times, the running time of the algorithm in worst case will be , or if then .

Our algorithm was described to determine the equivalence of two complete DFA's. If we have to determine the equivalence of two NFA's, first we transform them into complete DFA's and after this we can apply the above algorithm.

DFA-Equivalence()

  1  write in the first column of the first row the pair  
  2   
  3  REPEAT 
  4     
  5    let  be the pair in the first column of the th row 
  6    FOR all  
  7       DO write in the column associated to  in the th row 
                the pair 
  8          IF one state in  is final 
                   and the other not
  9             THEN RETURN NO 
 10             ELSE write pair  
                      in the next empty row of the first column,
                      if not occurred already in the first column
 11  UNTIL the first element of th row becomes empty 
 12  RETURN YES 

Example 1.11 Determine if the two DFA's in Fig. 1.6 are equivalent or not. The algorithm gives the table

The two DFA's are equivalent because all possible pairs of states are considered and in every pair both states are final or both are not final.

Figure 1.6.  Equivalent DFA's (Example 1.11).

Example 1.12 The table of the two DFA's in Fig. 1.7 is:

These two DFA's are not equivalent, because in the last column of the second row in the pair the first state is final and the second not.

Figure 1.7.  Non equivalent DFA's (Example 1.12).

We have seen that NFA's accept the same class of languages as DFA's. The following theorem states that this class is that of regular languages.

Theorem 1.11 If is a language accepted by a DFA, then one may construct a regular grammar which generates language .

Proof. Let be the DFA accepting language , that is . Define the regular grammar with the productions:

If for and , then put production in .

If and , then put also production in .

Prove that .

Let and . Thus, since accepts word , there is a walk

Then there are in the productions

(in the right-hand side of the last production does not occur, because ), so there is the derivation

Therefore, .

Conversely, let and . Then there exists a derivation

in which productions

were used, which by definition means that in DFA there is a walk

and since is a final state, .

If the DFA accepts also the empty word , then in the above grammar we introduce a new start symbol instead of , consider the new production and for each production introduce also .

Example 1.13 Let be a DFA, where . The corresponding transition table is

The transition graph of is in Fig. 1.8. By Theorem 1.11 we define regular grammar with the productions in

One may prove that .

Figure 1.8.  DFA of the Example 1.13.

The method described in the proof of Theorem 1.11 easily can be given as an algorithm. The productions of regular grammar obtained from the DFA can be determined by the following algorithm.

Regular-Grammar-from-DFA(A)

  1   
  2  FOR all  
  3    DO FOR all  
  4       DO FOR all  
  5          DO IF  
  6             THEN  
  7                IF  
  8                   THEN  
  9  IF  
 10    THEN  
 11  RETURN  

It is easy to see that the running time of the algorithm is , if the number of states is and the number of letter in alphabet is . In lines 2–4 we can consider only one loop, if we use the elements of . Then the worst case running time is , where is the number of transitions of DFA. This is also , since all transitions are possible. This algorithm is:

Regular-Grammar-from-Dfa'(A)

  1   
  2  FOR all  
  3    DO  
  4       IF  
  5          THEN  
  6  IF  
  7    THEN  
  8  RETURN  

Theorem 1.12 If is a regular language, then one may construct an NFA that accepts language .

Proof. Let be the grammar which generates language . Define NFA :

, where (i.e. is a new symbol),

For every production , define transition in .

For every production , define transition in .

Prove that .

Let , . Then there is in a derivation of word :

This derivation is based on productions

Then, by the definition of the transitions of NFA there exists a walk

Thus, . If , there is production , but in this case the initial state is also a final one, so . Therefore, .

Let now . Then there exists a walk

If is the empty word, then instead of we have in the above formula , which also is a final state. In other cases only can be as last symbol. Thus, in there exist the productions

and there is the derivation

thus, and therefore .

Example 1.14 Let be a regular grammar. The NFA associated is , where . The corresponding transition table is

The transition graph is in Fig. 1.9. This NFA can be simplified, states and can be contracted in one final state.

Figure 1.9.  NFA associated to grammar in Example 1.14.

Using the above theorem we define an algorithm which associate an NFA to a regular grammar .

NFA-from-Regular-Grammar(A)

  1   
  2   
  3  FOR all  
  4    DO FOR all  
  5       DO IF  
  6          THEN  
  7       FOR all  
  8          DO IF  
  9             THEN  
 10  IF  
 11    THEN  
 12    ELSE  
 13  RETURN A 

As in the case of algorithm REGULAR-GRAMMAR-FROM-DFA, the running time is , where is number of nonterminals and the number of terminals. Loops in lines 3, 4 and 7 can be replaced by only one, which uses productions. The running time in this case is better and is equal to , if is the number of productions. This algorithm is:

NFA-from-Regular-Grammar'(A)

  1   
  2   
  3  FOR all  
  4    DO IF  
  5       THEN  
  6    IF  
  7       THEN  
  8  IF  
  9    THEN  
 10    ELSE  
 11  RETURN A 

From Theorems 1.10, 1.11 and 1.12 results that the class of regular languages coincides with the class of languages accepted by NFA's and also with class of languages accepted by DFA's. The result of these three theorems is illustrated in Fig. 1.10 and can be summarised also in the following theorem.

Figure 1.10.  Relations between regular grammars and finite automata. To any regular grammar one may construct an NFA which accepts the language generated by that grammar. Any NFA can be transformed in an equivalent DFA. To any DFA one may construct a regular grammar which generates the language accepted by that DFA.

Theorem 1.13 The following three class of languages are the same:

the class of regular languages,

the class of languages accepted by DFA's,

the class of languages accepted by NFA's.

A finite automaton with -moves (FA with -moves) extends NFA in such way that it may have transitions on the empty input , i.e. it may change a state without reading any input symbol. In the case of a FA with -moves for the set of transitions it is true that .

The transition function of a FA with -moves is:

The FA with -moves in Fig. 1.11 accepts words of form , where and .

Figure 1.11.  Finite automata with -moves.

Theorem 1.14 To any FA with -moves one may construct an equivalent NFA (without -moves).

Let be an FA with -moves and we construct an equivalent NFA . The following algorithm determines sets and . For a state denote by the set of states (including even ) in which one may go from using -moves only. This may be extended also to sets

Clearly, for all and both and may be computed. Suppose in the sequel that these are given.

The following algorithm determine the transitions using the transition function , which is defined in line 5.

If and , then lines 2–6 show that the running time in worst case is .

Eliminate-Epsilon-Moves(A)

  1   
  2  FOR all  
  3    DO FOR all  
  4       DO  
  5           
  6   
  7  RETURN  

Example 1.15 Consider the FA with -moves in Fig. 1.11. The corresponding transition table is:

Apply algorithm ELIMINATE-EPSILON-MOVES.

, ,

, and its intersection with is not empty, thus .

,

.

,

,

,

,

.

The transition table of NFA is:

and the transition graph is in Fig. 1.12.

Figure 1.12.  NFA equivalent to FA with -moves given in Fig. 1.11.

Define regular operations on NFA: union, product and iteration. The result will be an FA with -moves.

Operation will be given also by diagrams. An NFA is given as in Fig. 1.13(a). Initial states are represented by a circle with an arrow, final states by a double circle.

Figure 1.13.  (a) Representation of an NFA. Initial states are represented by a circle with an arrow, final states by a double circle. (b) Union of two NFA's.

Let and be NFA. The result of any operation is a FA with -moves . Suppose that always. If not, we can rename the elements of any set of states.

Union. , where

,

,

,

,

.

For the result of the union see Fig. 1.13(b). The result is the same if instead of a single initial state we choose as set of initial states the union . In this case the result automaton will be without -moves. By the definition it is easy to see that .

Product. , where

,

,

,

,

.

For the result automaton see Fig. 1.14(a). Here also .

Figure 1.14.  (a) Product of two FA. (b) Iteration of an FA.

Iteration. , where

,

,

,

,

.

The iteration of an FA can be seen in Fig. 1.14(b). For this operation it is also true that .

The definition of these tree operations proves again that regular languages are closed under the regular operations.

A DFA is called minimum state automaton if for any equivalent complete DFA it is true that . We give an algorithm which builds for any complete DFA an equivalent minimum state automaton.

Figure 1.15.  Minimization of DFA.

States and of an DFA are equivalent if for arbitrary word we reach from both either final or nonfinal states, that is

if for any word

If two states are not equivalent, then they are distinguishable. In the following algorithm the distinguishable states will be marked by a star, and equivalent states will be merged. The algorithm will associate list of pair of states with some pair of states expecting a later marking by a star, that is if we mark a pair of states by a star, then all pairs on the associated list will be also marked by a star. The algorithm is given for DFA without inaccessible states. The used DFA is complete, so contains exact one element, function defined in Subsection 1.2.2, which gives the unique element of the set, will be also used here.

Automaton-Minimization()

  1  mark with a star all pairs of states  for which  and  or  and  
  2  associate an empty list with each unmarked pair  
  3  FOR all unmarked pair of states  and for all symbol  
          examine pairs of states 
          IF any of these pairs is marked,
             THEN mark also pair  with all the elements on the list before
                associated with pair 
             ELSE IF all the above pairs are unmarked
                THEN put pair  on each list associated with pairs
                   , unless 
  4  merge all unmarked (equivalent) pairs 

Figure 1.16.  Minimum automaton equivalent with DFA in Fig. 1.15.

After finishing the algorithm, if a cell of the table does not contain a star, then the states corresponding to its row and column index, are equivalent and may be merged. Merging states is continued until it is possible. We can say that the equivalence relation decomposes the set of states in equivalence classes, and the states in such a class may be all merged.

Remark. The above algorithm can be used also in the case of an DFA which is not complete, that is there are states for which does not exist transition. Then a pair may occur, and if is a final state, consider this pair marked.

Example 1.16 Let be the DFA in Fig. 1.15. We will use a table for marking pairs with a star. Marking pair means putting a star in the cell corresponding to row and column (or row and column ).

First we mark pairs , , , and (because is the single final state). Then consider all unmarked pairs and examine them as the algorithm requires. Let us begin with pair . Associate with it pairs , that is , . Because pair is already marked, mark also pair .

In the case of pair the new pairs are and . With pair associate pair on a list, that is

Now continuing with one obtain pairs and , with which nothing are associated by algorithm.

Continue with pair . The associated pairs are and . None of them are marked, so associate with them on a list pair , that is

Now continuing with we get the pairs and , and because this latter is marked we mark pair and also pair associated to it on a list. Continuing we will get the table in Fig. 1.15, that is we get that and . After merging them we get an equivalent minimum state automaton (see Fig. 1.16).

The following theorem, called pumping lemma for historical reasons, may be efficiently used to prove that a language is not regular. It is a sufficient condition for a regular language.

Theorem 1.15 (pumping lemma) For any regular language there exists a natural number (depending only on ), such that any word of with length at least may be written as such that

(1) ,

(2) ,

(3) for all .

Proof. If is a regular language, then there is such an DFA which accepts (by Theorems 1.12 and 1.10). Let be this DFA, so . Let be the number of its states, that is . Let and . Then, because the automaton accepts word , there are states and walk

Figure 1.17.  Sketch of DFA used in the proof of the pumping lemma.

Because the number of states is and , by the pigeonhole principle states can not all be distinct (see Fig. 1.17), there are at least two of them which are equal.

Footnote. Pigeonhole principle: If we have to put more than objects into boxes, then at least one box will contain at least two objects.

Let , where and is the least such index. Then . Decompose word as:

.

This decomposition immediately yields to and . We will prove that for any .

Because , there exists an walk

and because of , this may be written also as

From this walk can be omitted or can be inserted many times. So, there are the following walks:

Therefore for all , and this proves the theorem.

Example 1.17 We use the pumping lemma to show that is not regular. Assume that is regular, and let be the corresponding natural number given by the pumping lemma. Because the length of the word is , this word can be written as in the lemma. We prove that this leads to a contradiction. Let be the decomposition as in the lemma. Then , so and can contain no other letters than , and because we must have , word contains at least one . Then for will contain a different number of 's and 's, therefore for any . This is a contradiction with the third assertion of the lemma, this is why that assumption that is regular, is false. Therefore .

Because the context-free grammar generates language , we have . From these two follow that .

Example 1.18 We show that is not regular. ( is the number of 0's in , while the number of 1's).

We proceed as in the previous example using here word , where is the natural number associated by lemma to language .

Example 1.19 We prove, using the pumping lemma, that is not a regular language. Let be, where here is also the natural number associated to by the pumping lemma. From we have that contains no other letters than , but it contains at least one. By lemma we have , that is not possible. Therefore is not regular.

Pumping lemma has several interesting consequences.

Corollary 1.16 Regular language is not empty if and only if there exists a word , , where is the natural number associated to by the pumping lemma.

Proof. The assertion in a direction is obvious: if there exists a word shorter than in , then . Conversely, let and let be the shortest word in . We show that . If , then we apply the pumping lemma, and give the decomposition , and . This is a contradiction, because and is the shortest word in . Therefore .

Corollary 1.17 There exists an algorithm that can decide if a regular language is or not empty.

Proof. Assume that , where is a DFA. By Consequence 1.16 and Theorem 1.15 language is not empty if and only if it contains a word shorter than , where is the number of states of automaton . By this it is enough to decide that there is a word shorter than which is accepted by automaton . Because the number of words shorter than is finite, the problem can be decided.

When we had given an algorithm for inaccessible states of a DFA, we remarked that the procedure can be used also to decide if the language accepted by that automaton is or not empty. Because finite automata accept regular languages, we can consider to have already two procedures to decide if a regular languages is or not empty. Moreover, we have a third procedure, if we take into account that the algorithm for finding productive states also can be used to decide on a regular language when it is empty.

Corollary 1.18 A regular language is infinite if and only if there exists a word such that , where is the natural number associated to language , given by the pumping lemma.

Proof. If is infinite, then it contains words longer than , and let be the shortest word longer than in . Because is regular we can use the pumping lemma, so , where , thus is also true. By the lemma . But because and the shortest word in longer than is , we get . From we get also .

Conversely, if there exists a word such that , then using the pumping lemma, we obtain that , and for any , therefore is infinite.

Now, the question is: how can we apply the pumping lemma for a finite regular language, since by pumping words we get an infinite number of words? The number of states of a DFA accepting language is greater than the length of the longest word in . So, in there is no word with length at least , when is the natural number associated to by the pumping lemma. Therefore, no word in can be decomposed in the form , where , , , and this is why we can not obtain an infinite number of words in .

In this subsection we introduce for any alphabet the notion of regular expressions over and the corresponding representing languages. A regular expression is a formula, and the corresponding language is a language over . For example, if , then , , are regular expressions over which represent respectively languages , , . The exact definition is the following.

Definition 1.19 Define recursively a regular expression over and the language it represent.

is a regular expression representing the empty language.

is a regular expression representing language .

If , then is a regular expression representing language .

If , are regular expressions representing languages and respectively, then , , are regular expressions representing languages , and respectively.

Regular expression over can be obtained only by using the above rules a finite number of times.

Some brackets can be omitted in the regular expressions if taking into account the priority of operations (iteration, product, union) the corresponding languages are not affected. For example instead of we can consider .

Two regular expressions are equivalent if they represent the same language, that is if , where and are the languages represented by regular expressions and respectively. Figure 1.18 shows some equivalent expressions.

Figure 1.18.  Properties of regular expressions.

We show that to any finite language can be associated a regular expression which represent language . If , then . If , then , where for any expression is a regular expression representing language . This latter can be done by the following rule. If , then , else if , where depends on , then , where the brackets are omitted. We prove the theorem of Kleene which refers to the relationship between regular languages and regular expression.

Theorem 1.20 (Kleene's theorem) Language is regular if and only if there exists a regular expression over representing language .

Proof. First we prove that if is a regular expression, then language which represents is also regular. The proof will be done by induction on the construction of expression.

If , , , then , , respectively. Since is finite in all three cases, it is also regular.

If , then , where and are the languages which represent the regular expressions and respectively. By the induction hypothesis languages and are regular, so is also regular because regular languages are closed on union. Cases and can be proved by similar way.

Conversely, we prove that if is a regular language, then a regular expression can be associated to it, which represent exactly the language . If is regular, then there exists a DFA for which . Let the states of the automaton . Define languages for all and . is the set of words, for which automaton goes from state to state without using any state with index greater than . Using transition graph we can say: a word is in , if from state we arrive to state following the edges of the graph, and concatenating the corresponding labels on edges we get exactly that word, not using any state . Sets can be done also formally:

, if ,

,

for all .

We can prove by induction that sets can be described by regular expressions. Indeed, if , then for all and languages are finite, so they can be expressed by regular expressions representing exactly these languages. Moreover, if for all and language can be expressed by regular expression, then language can be expressed also by regular expression, which can be corresponding constructed from regular expressions representing languages , , and respectively, using the above formula for .

Finally, if is the set of final states of the DFA , then can be expressed by a regular expression obtained from expressions representing languages using operation .

Further on we give some procedures which associate DFA to regular expressions and conversely regular expression to DFA.

Associating regular expressions to finite automata.

We present here three methods, each of which associate to a DFA the corresponding regular expression.

Method 1. Using the result of the theorem of Kleene, we will construct the sets , and write a regular expression which represents the language , where is the set of final states of the automaton.

Figure 1.19.  DFA from Example 1.20, to which regular expression is associated by Method 1.

Figure 1.20.  DFA in Example 1.21 to which a regular expression is associated by Method 1. The computation are in Figure 1.21.

Figure 1.21.  Determining a regular expression associated to DFA in Figure 1.20 using sets .

Example 1.20 Consider the DFA in Fig. 1.19.

Then the regular expression corresponding to is .

Example 1.21 Find a regular expression associated to DFA in Fig. 1.20. The computations are in Figure 1.21. The regular expression corresponding to is .

Method 2. Now we generalize the notion of finite automaton, considering words instead of letters as labels of edges. In such an automaton each walk determine a regular expression, which determine a regular language. The regular language accepted by a generalized finite automaton is the union of regular languages determined by the productive walks. It is easy to see that the generalized finite automata accept regular languages.

The advantage of generalized finite automata is that the number of its edges can be diminuted by equivalent transformations, which do not change the accepted language, and leads to a graph with only one edge which label is exactly the accepted language. The possible equivalent transformations can be seen in Fig. 1.22. If some of the vertices 1, 2, 4, 5 on the figure coincide, in the result they are merged, and a loop will arrive.

First, the automaton is transformed by corresponding -moves to have only one initial and one final state. Then, applying the equivalent transformations until the graph will have only one edge, we will obtain as the label of this edge the regular expression associated to the automaton.

Figure 1.22.  Possible equivalent transformations for finding regular expression associated to an automaton.

Figure 1.23.  Transformation of the finite automaton in Fig. 1.19.

Example 1.22 In the case of Fig. 1.19 the result is obtained by steps illustrated in Fig. 1.23. This result is , which represents the same language as obtained by Method 1 (See example 1.20).

Example 1.23 In the case of Fig. 1.20 is not necessary to introduce new initial and final state. The steps of transformations can be seen in Fig. 1.23. The resulted regular expression can be written also as , which is the same as obtained by the previous method.

Figure 1.24.  Steps of Example 1.23.

Method 3. The third method for writing regular expressions associated to finite automata uses formal equations. A variable is associated to each state of the automaton (to different states different variables). Associate to each state an equation which left side contains , its right side contains sum of terms of form or , where is a variable associated to a state, and is its corresponding input symbol. If there is no incoming edge in the state corresponding to then the right side of the equation with left side contains , otherwise is the sum of all terms of the form for which there is a transition labelled with letter from state corresponding to to the state corresponding to . If the state corresponding to is also an initial and a final state, then on right side of the equation with the left side will be also a term equal to . For example in the case of Fig. 1.20 let these variable corresponding to the states . The corresponding equation are

.

If an equation is of the form , where are arbitrary words not containing , then it is easy to see by a simple substitution that is a solution of the equation.

Because these equations are linear, all of them can be written in the form or , where do not contain any variable. Substituting this in the other equations the number of remaining equations will be diminuted by one. In such a way the system of equation can be solved for each variable.

The solution will be given by variables corresponding to final states summing the corresponding regular expressions.

In our example from the first equation we get . From here , or , and solving this we get . Variable can be obtained immediately and we obtain .

Using this method in the case of Fig. 1.19, the following equations will be obtained

Therefore

.

Adding the two equations we will obtain

, from where (considering as and as ) we get the result

.

From here the value of after the substitution is

,

which is equivalent to the expression obtained using the other methods.

Associating finite automata to regular expressions.

Associate to the regular expression a generalized finite automaton:

After this, use the transformations in Fig. 1.25 step by step, until an automaton with labels equal to letters from or will be obtained.

Example 1.24 Get started from regular expression . The steps of transformations are in Fig. 1.26(a)-(e). The last finite automaton (see Fig. 1.26(e)) can be done in a simpler form as can be seen in Fig. 1.26(f). After eliminating the -moves and transforming in a deterministic finite automaton the DFA in Fig. 1.27 will be obtained, which is equivalent to DFA in Fig. 1.19.

Figure 1.25.  Possible transformations to obtain finite automaton associated to a regular expression.

Figure 1.26.  Associating finite automaton to regular expression .

Figure 1.27.  Finite automaton associated to regular expression .

Exercises

1.2-1 Give a DFA which accepts natural numbers divisible by 9.

1.2-2 Give a DFA which accepts the language containing all words formed by

a. an even number of 0's and an even number of 1's,

b. an even number of 0's and an odd number of 1's,

c. an odd number of 0's and an even number of 1's,

d. an odd number of 0's and an odd number of 1's.

1.2-3 Give a DFA to accept respectively the following languages:

.

1.2-4 Give an NFA which accepts words containing at least two 0's and any number of 1's. Give an equivalent DFA.

1.2-5 Minimize the DFA's in Fig. 1.28.

Figure 1.28.  DFA's to minimize for Exercise 1.2-5

1.2-6 Show that the DFA in 1.29.(a) is a minimum state automaton.

Figure 1.29.  Finite automata for Exercises 1.2-6 and 1.2-7.

1.2-7 Transform NFA in Fig. 1.29.(b) in a DFA, and after this minimize it.

1.2-8 Define finite automaton which accepts all words of the form (), and finite automaton which accepts all words of the form (). Define the union automaton , and then eliminate the -moves.

1.2-9 Associate to DFA in Fig. 1.30 a regular expression.

Figure 1.30.  DFA for Exercise1.2-9.

1.2-10 Associate to regular expression a DFA.

1.2-11 Prove, using the pumping lemma, that none of the following languages are regular:

.

1.2-12 Prove that if is a regular language, then is also regular.

1.2-13 Prove that if is a regular language, then the following languages are also regular.

.

1.2-14 Show that the following languages are all regular.

,

,

.

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.

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

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 (see Example 1.27).

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.

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

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:

,

.

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 .

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 .

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.

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

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

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.

The exact definition of symbolic units would be given by regular grammar, regular expressions or deterministic finite automaton. The theories of regular grammars, regular expressions and deterministic finite automata were studied in previous chapters.

Practically the lexical analyser may be a part of the syntactic analysis. The main reason to distinguish these analysers is that a lexical analyser made from regular grammar is much more simpler than a lexical analyser made from a context-free grammar. Context-free grammars are used to create syntactic analysers.

One of the most popular methods to create the lexical analyser is the following:

We note that, in writing of symbols regular expressions are used, because they are more comfortable and readable then regular grammars. There are standard programs as the lex of UNIX systems, that generate a complete syntactical analyser from regular expressions. Moreover, there are generator programs that give the automaton of scanner, too.

A very trivial implementation of the deterministic finite automaton uses multidirectional cASE instructions. The conditions of the branches are the characters of state transitions, and the instructions of a branch represent the new state the automaton reaches when it carries out the given state transition.

The main principle of the lexical analyser is building a symbol from the longest series of symbols. For example the string ABC is a three-letters symbol, rather than three one-letter symbols. This means that the alternative instructions of the cASE branch read characters as long as they are parts of a constructed symbol.

Functions can belong to the final states of the automaton. For example, the function converts constant symbols into an inner binary forms of constants, or the function writes identifiers to the symbol table.

The input stream of the lexical analyser contains tabulators and space characters, since the source-handler expunges the carriage return and line feed characters only. In most programming languages it is possible to write a lot of spaces or tabulators between symbols. In the point of view of compilers these symbols have no importance after their recognition, hence they have the name white spaces.

Expunging white spaces is the task of the lexical analyser. The description of the white space is the following regular expression:

where space and the tab tabulator are the characters which build the white space symbols and is the symbol for the or function. No actions have to make with this white space symbols, the scanner does not pass these symbols to the syntactic analyser.

Some examples for regular expression:

Example 2.1 Introduce the following notations: Let be an arbitrary digit, and let be an arbitrary letter,

the not-visible characters are denoted by their short names, and let be the name of the empty character stream. denotes a character distinct from . The regular expressions are:

Figure 2.4.  The positive integer and real number.

Deterministic finite automata constructed from regular expressions 2 and 3 are in Figures 2.4 and 2.5.

Figure 2.5.  The identifier.

The task of lexical analyser is to determine the text of symbols, but not all the characters of a regular expression belong to the symbol. As is in the 6th example, the first and the last " characters do not belong to the symbol. To unravel this problem, a buffer is created for the scanner. After recognising of a symbol, the characters of these symbols will be in the buffer. Now the deterministic finite automaton is supplemented by a transfer function, where means that the character is inserted into the buffer.

Figure 2.6.  A comment.

Example 2.2 The 4th and 6th regular expressions of the example 2.1 are supplemented by the function, automata for these expressions are in Figures 2.6 and 2.7. The automaton of the 4th regular expression has none function, since it recognises comments. The automaton of the 6th regular expression recognises This is a “string” from the character string ”This is a “”string”””.

Figure 2.7.  The character string.

Now we write the algorithm of the lexical analyser given by deterministic finite automaton. (The state of the set of one element will be denoted by the only element of the set).

Let be the deterministic finite automaton, which is the scanner. We augment the alphabet with a new notion: let others be all the characters not in . Accordingly, we modify the transition function :

The algorithm of parsing, using the augmented automaton , follows:

Lex-analyse()

  1  ,  first character of  
  2   
  3  WHILE  and  
  4    DO IF  
  5       THEN  
  6           next character of  
  7       ELSE  
  8  IF  and  
  9    THEN  
 10  ELSE  
 11  RETURN  

The algorithm has two parameters: the first one is the input character string terminated by , the second one is the automaton of the scanner. In the line 1 the state of the scanner is set to , to the start state of the automaton, and the first character of the input string is determined. The variable indicates that the algorithm is analysing the input string, the text analysing is set in this variable in the line 2. In the line 5 a state-transition is executed. It can be seen that the above augmentation is needed to terminate in case of unexpected, invalid character. In line 8–10 the O.K. means that the analysed character string is correct, and the ERROR signs that a lexical error was detected. In the case of successful termination the variable contains the character, at erroneous termination it contains the invalid character.

We note that the algorithm LEX-ANALYSE recognise one symbol only, and then it is terminated. The program written in a programming language consists of a lot of symbols, hence after recognising a symbol, the algorithm have to be continued by detecting the next symbol. The work of the analyser is restarted at the state of the automaton. We propose the full algorithm of the lexical analyser as an exercise (see Problem 2-1).

Example 2.3 The automaton of the identifier in the point 3 of example 2.1 is in Figure 2.5. The start state is 0, and the final state is 1. The transition function of the automaton follows:

The augmented transition function of the automaton:

The algorithm LEX-ANALYSE gives the series of states and sign O.K. to the input string abc123#, it gives sign ERROR to the input sting 9abc#, and the series and sign ERROR to the input string abc 123.

In this subsection we investigate the problems emerged during running of lexical analyser, and supply solutions for these problems.

       begin
          begin; begin end; end; begin end; 
       end;

Look ahead.

Since the lexical analyser creates a symbol from the longest character stream, the lexical analyser has to look ahead one or more characters for the allocation of the right-end of a symbol. There is a classical example for this problem, the next two FORTRAN statements:

DO 10 I = 1.1000

DO 10 I = 1,1000

In the FORTRAN programming language space-characters are not important characters, they do not play an important part, hence the character between 1 and 1000 decides that the statement is a DO cycle statement or it is an assignment statement for the DO10I identifier.

To sign the right end of the symbol, we introduce the symbol / into the description of regular expressions. Its name is lookahead operator. Using this symbol the description of the above DO keyword is the next

This definition means that the lexical analyser says that the first two D and O letters are the DO keyword, if looking ahead, after the O letter, there are letters or digits, then there is an equal sign, and after this sign there are letters or digits again, and finally, there is a “,” character. The lookahead operator implies that the lexical analyser has to look ahead after the DO characters. We remark that using this lookahead method the lexical analyser recognises the DO keyword even if there is an error in the character stream, such as in the DO2A=3B, character stream, but in a correct assignment statement it does not detect the DO keyword.

In the next example we concern for positive integers. The definition of integer numbers is a prefix of the definition of the real numbers, and the definition of real numbers is a prefix of the definition of real numbers containing explicit power-part.

The automaton for all of these three expressions is the automaton of the longest character stream, the real number containing explicit power-part.

The problem of the lookahead symbols is resolved using the following algorithm. Put the character into a buffer, and put an auxiliary information aside this character. This information is “it is invalid”. If the character string, using this red character, is not correct; otherwise we put the type of the symbol into here. If the automaton is in a final-state, then the automaton recognises a real number with explicit power-part. If the automaton is in an internal state, and there is no possibility to read a next character, then the longest character stream which has valid information is the recognised symbol.

Example 2.4 Consider the 12.3e+f# character stream, where the character # is the endsign of the analysed text. If in this character stream there was a positive integer number in the place of character f, then this character stream should be a real number. The content of the puffer of lexical analyser:

The recognised symbol is the 12.3 real number. The lexical analysing is continued at the text e+f.

The number of lookahead-characters may be determined from the definition of the program language. In the modern languages this number is at most two.

If we analyse from top to down then we start with the start symbol. This symbol is the root of syntax tree; we attempt to construct the syntax tree. Our goal is that the leaves of tree are the terminal symbols.

First we review the notions that are necessary in the top-down parsing. Then the table methods and the recursive descent method will be analysed.

grammars

Our methods build the syntax tree top-down and read symbols of the program left to right. For this end we try to create terminals on the left side of sentential forms.

Definition 2.4 If then the leftmost direct derivation of the sentential form () is , and

Definition 2.5 If all of direct derivations in () are leftmost, then this derivation is said to be leftmost derivation, and

In a leftmost derivation terminal symbols appear at the left side of the sentential forms. Therefore we use leftmost derivations in all of top-down parsing methods. Hence if we deal with top-down methods, we do not write the text “leftmost” at the arrows.

One might as well say that we create all possible syntax trees. Reading leaves from left to right, we take sentences of the language. Then we compare these sentences with the parseable text and if a sentence is same as the parseable text, then we can read the steps of parsing from the syntax tree which is belongs to this sentence. But this method is not practical; generally it is even impossible to apply.

A good idea is the following. We start at the start symbol of the grammar, and using leftmost derivations we try to create the text of the program. If we use a not suitable derivation at one of steps of parsing, then we find that, at the next step, we can not apply a proper derivation. At this case such terminal symbols are at the left side of the sentential form, that are not same as in our parseable text.

For the leftmost terminal symbols we state the theorem as follows.

Theorem 2.6 If () és , then .

The proof of this theorem is trivial. It is not possible to change the leftmost terminal symbols of sentential forms using derivation rules of a context free grammar.

This theorem is used during the building of syntax tree, to check that the leftmost terminals of the tree are same as the leftmost symbols of the parseable text. If they are different then we created wrong directions with this syntax tree. At this case we have to make a backtrack, and we have to apply an other derivation rule. If it is impossible (since for example there are no more derivation rules) then we have to apply a backtrack once again.

General top-down methods are realized by using backtrack algorithms, but these backtrack steps make the parser very slow. Therefore we will deal only with grammars such that have parsing methods without backtracks.

The main properties of grammars are the following. If, by creating the leftmost derivation (), we obtain the sentential form () at some step of this derivation, and our goal is to achieve , then the next step of the derivation for nonterminal is determinable unambiguously from the first symbols of .

To look ahead symbols we define the function .

Definition 2.7 Let be the set as follows.

The set consists of the first symbols of ; for , it consists the full . If , then .

Definition 2.8 The grammar is a grammar , if for derivations

() the equality

implies

Using this definition, if a grammar is a grammar then the symbol after the parsed determine the next derivation rule unambiguously (Figure 2.8).

Figure 2.8.  grammar.

One can see from this definition that if a grammar is an grammar then for all it is also an grammar. If we speak about grammar then we also mean that is the least number such that the properties of the definition are true.

Example 2.5 The next grammar is a grammar. Let be a grammar whose derivation rules are:

We have to use the derivation for the start symbol if the next symbol of the parseable text is or . We use the derivation if the next symbol is the mark #.

Example 2.6 The next grammar is a grammar. Let be a grammar whose the derivation rules are:

One can see that at the last step of derivations

and

if we look ahead one symbol, then in both derivations we obtain the symbol . The proper rule for symbol is determined to look ahead two symbols ( or ).

There are context free grammars such that are not grammars. For example the next grammar is not grammar for any .

Example 2.7 Let be a grammar whose the derivation rules are:

consists of sentences és . If we analyse the sentence , then at the first step we can not decide by looking ahead symbols whether we have to use the derivation or , since for all .

By the definition of the grammar, if we get the sentential form using leftmost derivations, then the next symbol determines the next rule for symbol . This is stated in the next theorem.

Theorem 2.9 Grammar is a grammar iff

implies

If there is a rule in the grammar, then the set consists the length prefixes of terminal series generated from . It implies that, for deciding the property , we have to check not only the derivation rules, but also the infinite derivations.

We can give good methods, that are used in the practice, for grammars only. We define the follower-series, which follow a symbol or series of symbols.

Definition 2.10 , and if , then () .

The second part of the definition is necessary because if there are no symbols after the in the derivation , that is , then the next symbol after is the mark # only.

() consists of terminal symbols that can be immediately after the symbol in the derivation

Theorem 2.11 The grammar is a grammar iff, for all nonterminal and for all derivation rules ,

In this theorem the expression means that we have to concatenate to the elements of set separately, and for all elements of this new set we have to apply the function .

It is evident that Theorem 2.11 is suitable to decide whether a grammar is or it is not.

Hence forward we deal with languages determined by grammars, and we investigate the parsing methods of languages. For the sake of simplicity, we omit indexes from the names of functions és .

The elements of the set are determined using the next algorithm.

First()

  1  IF  
  2    THEN  
  3  IF , where  
  4    THEN  
  5  IF , where  
  6    THEN IF  
  7       THEN  
  8       ELSE  
  9       FOR all   
 10          DO  
 11             FOR  TO  
 12                DO IF  
 13                   THEN  
 14             IF  
 15                THEN  
 16  IF  
 17    THEN  
 18       FOR  TO  
 19          DO IF  
 20             THEN  
 21       IF  
 22          THEN  
 23  RETURN   

In lines 1–4 the set is given for and a terminal symbol . In lines 5–15 we construct the elements of this set for a nonterminal . If is derivated from then we put symbol into the set in lines 6–7 and 14–15. If the argument is a symbol stream then the elements of the set are constructed in lines 16–22. We notice that we can terminate the fOR cycle in lines 11 and 18 if , since in this case it is not possible to derive symbol from .

In Theorem 2.11 and hereafter, it is necessary to know the elements of the set . The next algorithm constructs this set.

Follow()

  1  IF  
  2    THEN  
  3    ELSE  
  4  FOR all rules  
  5    DO IF  
  6       THEN  
  7          IF  
  8             THEN  
  9       ELSE  
 10  RETURN  

The elements of the set get into the set . In lines 4–9 we check that, if the argumentum is at the right side of a derivation rule, what symbols may stand immediately after him. It is obvious that no is in this set, and the symbol is in the set only if the argumentum is the rightmost symbol of a sentential form.