An alphabet is a finite nonempty set of symbols. We can use the union, the intersection and the relative complement set operations over the alphabet. The absolute complement operation can be used if a universe set is defined.

Example 1. Let the alphabet E be the English alphabet, the alphabet V contains the vowels, and the alphabet C is the set of the consonants. Then V∪C=E, V∩C=∅ and

A word is a finite sequence of symbols of the alphabet. The length of the word is the number of symbols it is composed of, with repetitions. Two words are equal if they have the same length and they have the same letter in each position. This might sound trivial, but let us see the following example:

Example 2. Let the alphabet V={1,2,+} and the words p=1+1, q=2. In this case 1+1≠ 2, i.e. p≠q, because these two words have different lengths, and also different letters in the first position.

There is a special operation on words called concatenation, this is the operation of joining two words end to end.

Example 3. Let the alphabet E be the English alphabet. Let the word p=railway, and the word q=station over the alphabet E. Then, the concatenation of p and q is p· q=railwaystation. The length of p is ∣p∣=7 and the length of q is ∣q∣=7, as well.

If there is no danger of confusion we can omit the dot from between the parameters of the concatenation operation. It is obvious that the equation ∣pq∣=∣p∣+∣q∣ holds for all words p and q. There is a special word called an empty word, whose length is 0 and denoted by λ. The empty word is the identity element of the concatenation operation, λp=pλ=p holds for each word p over any alphabet. The word u is a prefix of the word p if there exists a word w such that p=uw, and the word w is a suffix of the word p if there exists a word u such that p=uw. The word v is a subword of word p if there exists words u,w such that p=uvw. The word u is a proper prefix of the word p, if it is a prefix of p, and the following properties hold: u≠λ and u≠p. The word w is a proper suffix of the word p, if it is a suffix of p, and w≠λ, w≠ p. The word v is a proper subword of the word p, if it is a subword of p, and v≠λ, v≠p. As you can see, both the prefixes and suffixes are subwords, and both the proper prefixes and proper suffixes are proper subwords, as well.

Example 4. Let the alphabet E be the English alphabet. Let the word p=railwaystation, and the words u=rail, v=way and w=station. In this example, the word u is a prefix, the word w is a suffix and the word v is a subword of the word p. However, the word uv is also a prefix of the word p, and it is a subword of the word p, as well. The word uvw is a suffix of the word p, but it is not a proper suffix.

We can use the exponentiation operation on a word in a classical way, as well. p⁰=λ by definition, p¹=p, and pⁱ=p^i-1p, for each integer i ≥ 2. The union of pⁱ for each integer i ≥ 0 is denoted by p^*, and the union of pⁱ for each integer i ≥ 1 is denoted by p⁺. These operations are called Kleene star and Kleene plus operations. p^*=p⁺∪{λ} holds for each word p, and if p≠λ then p⁺=p^* \ {λ}. We can also use the Kleene star and Kleene plus operations on an alphabet. For an alphabet V we denote the set of all words over the alphabet by V ^*, and the set of all words, but the empty word by V ⁺.

A language over an alphabet is not necessarily a finite set of words, and it is usually denoted by L. For a given alphabet V the language L over V is L ⊆ V ^*. We have a set again, so we can use the classical set operations, union, intersection, and the complement operation, if the operands are defined over the same alphabet. For the absolute complement operation we use V ^* for universe, so We can also use the concatenation operation. The concatenation of the languages L₁ and L₂ contains all words pq where p ∈ L₁ and q ∈ L₂. The exponentiation operation is defined in a classical way, as well. L⁰={λ} by definition, L¹=L, and Lⁱ=L^i-1· L, for each integer i ≥ 2. The language L ⁰ contains exactly one word, the empty word. The empty language does not contain any words, L_e=∅, and L ⁰ ≠ L_e. We can also use the Kleene star and Kleene plus closure for languages. so L^*=L ⁺ if and only if λ ∈ L.

The algebraic approach to formal languages can be useful for readers who prefer the classical mathematical models. The free monoid on an alphabet V is the monoid whose elements are from V ^*. From this point of view both operations, concatenation, (also called product) - which is not a commutative operation in this case -, and the union operation (also called addition), create a free monoid on set V, because these operations are associative, and they both have an identity element.

The equation L_e · L₁ = L₁ · L_e = L_e also holds for each L₁ ⊆ V ^*.

In this section, the definition of basic rewriting systems in general and a specific one, the Markov algorithm is presented.

Definition 1. A formal system (or rewriting system) is a pair W = ( V, P ), where V is an alphabet and P is a finite subset of the Cartesian product V ^*× V ^*. The elements of P are the (rewriting) rules or productions. If ( p, q ) ∈ P, then we usually write it in the form p → q. Let r, s ∈ V ^*, and we say that s can be directly derived (or derived in one step) from r (formally: r ⇒ s) if there are words p, p', p'', q ∈ V ^* such that r = p' pp'', s = p' qp'' and p → q ∈ P. The word s can be derived from r (formally: r ⇒ ^* s) if there is a sequence of words r₀, r₁, ..., r_k ( k ≥ 1 ) such that r₀ = r, r_k = s and r_i ⇒ r_i+1 holds for every 0 ≤ i < k. Moreover, we consider the relation r ⇒^* r for every word r ∈ V ^*. (Actually, the relation ⇒^* is the reflexive and transitive closure of the relation ⇒.

A rewriting (or derivation) step can be understood as follows: the word s can be obtained from the word r in such a way that in s the right hand side q of a production of P is written instead of the left hand side p of the same production in r.

Example 5. Let W = ( V, P ) with V = { a, b, c, e, l, n, p, r, t } and P = { able → can, r → c, pp → b }. Then applerat ⇒ applecat ⇒ ablecat ⇒ cancat, and thus applerat ⇒^* cancat in the system W.

Now, we are going to present a special version of the rewriting systems that is deterministic, and was given by the Russian mathematician A. A. Markov as normal algorithms.

Definition 2. M = ( V, P, H ) is a Markov (normal) algorithm where

The execution of the algorithm on input w ∈ V ^* is as follows:

We note here that rules of type λ → q also can be applied to insert word q to the beginning of the current (input) word.

The Markov algorithm may be terminated with an output, or may work forever (infinite loop).

Example 6. Let M = ({1,2,3 },{21→ 12, 31→ 13, 32→ 23},{}) be a Markov algorithm. Then, it is executed to the input 1321 as follows:

Since there are no more applicable productions, it is terminated. Actually, it is ordering the elements of the input word in a non-decreasing way.

Example 7. Let

Let us apply the algorithm W to the input

As it can be seen in Animation 1, the output is

(For better understanding in the Animation the productions of the algorithm is numbered.)

Animation 1.

Exercise 1. Execute the Markov algorithm

on the following input words:

Exercise 2. Execute the Markov algorithm M = ({1,×, a,b },

{ × 11 → a × 1, × 1 → a, 1a → a1b, ba → ab, b1 → 1b, a1 → a, ab → b, b → 1 } ,{ })

on the following input words:

The previous two exercises are examples for Markov algorithms that compute unary addition and unary multiplication, respectively.

It is important to know that this model of the algorithm is universal in the sense that every problem that can be solved in an algorithmic way can be solved by a Markov algorithm as well.

In the next section, other variations of the rewriting systems are shown: the generative grammars, which are particularly highlighted in this book. As we will see, the generative grammars use their productions in a non-deterministic way.

The generative grammar is a universal method to define languages. It was introduced by Noam Chomsky in the 1950s. The formal definition of the generative grammar is the following:

Definition 3. The generative grammar (G) is the following quadruple:

where

The following properties hold: N ∩ T = ∅ and S ∈ N.

Let us denote the union of the sets N and T by V ( V = N ∪ T). Then, the form of the production rules is V ^*N V ^* → V ^*.

Informally, we have two disjoint alphabets, the first alphabet contains the so called start symbol, and we also have a set of productions. The productions have two sides, both sides are words over the joint alphabet, and the word on the left hand side must contain a nonterminal symbol. We have a special notation for the production rules. Let the word p be the left hand side of the rule, and the word q be the right hand side of the rule, then we use the p → q ∈ P expression.

Example 8. Let the generative grammar G be G = ( N, T, S, P ), where

N = {S,A},
T = {a,b}, and
P = {
  S → bAbS,
  bAb → bSab,
  A → λ,
  S → aa
}.

In order to understand the operation of the generative grammar, we have to describe how we use the production rules to generate words. First of all, we should give the definition of the derivation.

Definition 4. Let G = ( N, T, S, P ) be a generative grammar, and let p and q be words over the joint alphabet V = N ∪ T. We say that the word q can be derived in one step from the word p, if p can be written in a form p = uxw, q can be written in a form q = uyw, and x → y ∈ P. (Denoted by p ⇒ q.) The word q can be derived from the word p, if q = p or there are words r₁, r₂,..., r_n such that r₁ = p, r_n = q and the word r_i can be derived in one step from the word r_i-1, for each 2 ≤ i ≤ n. (Denoted by p ⇒^* q.)

Now, that we have a formal definition of the derivation, let us see an example for deeper understanding.

Example 9. Let the generative grammar G be G = ( N, T, S, P ) , where

N = {S,A},
T = {0,1}, and
P = {
  S → 1,
  S → 1A,
  A → AA,
  A → 0,
  A → 1
}.

Let the words p,t and q be p = A0S0, t = A01A0, and q = A0110. In this example, the word t can be derived from the word p in one step, (p → t), because p can be written in a form p = uxw, where u = A0, x = S, w = 0, and the word t can be written in a form t = uyw, where y = 1A, and S → 1A ∈ P.

The word q can be derived from the word p, (p ⇒^*q), because there exist words r₁,r₂ and r₃ such that r₁ = p, r₂ = t, r₃ = q and r₁ ⇒ r₂ and r₂ ⇒ r₃.

Now we have all the definitions to demonstrate how we can use the generative grammar to generate a language.

Definition 5. Let G = ( N, T, S, P ) be a generative grammar. The language generated by the grammar G is

The above definition claims that the language generated by the grammar G contains each word over the terminal alphabet which can be derived from the start symbol S.

Example 10. Let the generative grammar G be G = ( N, T, S, P ), where

N = {S,A},
T = {a,b}, and
P = {
  S → bb,
  S → ASA,
  A → a
}.

In this example, the word bb can be derived from the start symbol S in one step, because S → bb ∈ P, so the word bb is in the generated language, bb ∈ L(G).

The word abba can be derived from the start symbol, because S ⇒ ASA, ASA ⇒ aSA, aSA ⇒ abbA, abbA → abba, so the word abba is also in the generated language, abba ∈ L(G).

The word bab can not be derived from the start symbol, so it is not in the generated language, bab ∉ L(G).

In this case, it is easy to determine the generated language, L(G) = {aⁱbbaⁱ∣i ≥ 0}.

Exercise 3. Create a generative grammar G, which generates the language L = {a^*b⁺c^*}!

Exercise 4. Create a generative grammar G, which generates the language of all binary numbers!

The Chomsky hierarchy was described first by Noam Chomsky in 1956. It classifies the generative grammars based on the forms of their production rules. The Chomsky hierarchy also classifies languages, based on the classes of generative grammars generating them. The formal definition is provided below.

Definition 6. (Chomsky hierarchy) Let G = ( N, T, S, P ) be a generative grammar.

Example 11. Let the generative grammar G₀ be

G0 = ({S,X},{x,y},S,P)
P = {
  S → SXSy,
  XS → y,
  X → SXS,
  S → yxx
  }.

This grammar is unrestricted, because the second rule is not a context-sensitive rule.

Example 12. Let the generative grammar G₁ be

G1 = ({S,X},{x,y},S,P)
P = {
  S → SXSy,
  XSy → XyxXy,
  S → yXy,
  X → y
  }.

This grammar is context-sensitive, because each production rule has an appropriate form.

Example 13. Let the generative grammar G₂ be

G2 = ({S,X},{x,y},S,P)
P = {
  S → SyS,
  S → XX,
  S → yxy,
  X → ySy,
  X → λ
}.

This grammar is context-free, because the left hand side of each production rule is a nonterminal symbol.

Example 14. Let the generative grammar G be

G = ({S,X},{x,y},S,P)
P = {
  S → xyS,
  S → X,
  X → yxS,
  S → x,
  X → λ
}.

This grammar is regular, because the left hand side of each production rule is a nonterminal, and the right hand side contains at most one nonterminal symbol, in last position.

Exercise 5. What is the type of the following grammars?

  1. G = ({S,A},{0,1},S,P)
     P = {
     S → 0101A,
     S → λ,
     A → 1S,
     A → 000
     }.
     
  2. G = ({S,A,B},{0,1},S,P)
     P = {
     S → 0A01B,
     S → λ,
     0A01 → 01A101,
     A → 0BB1,
     B → 1A1B,
     B → 0011,
     A → 1
     }.
     
  3. G = ({S,A,B},{0,1},S,P)
     P = {
     S → 0ABS1,
     S → 10,
     0AB → 01SAB,
     1SA → 111,
     A → 0,
     B → 1
     }.
     
  4. G = ({S,A},{0,1},S,P)
     P = {
     S → 00A,
     S → λ,
     A → λ,
     A → S1S
     }.

Definition 7. The language L is regular, if there exists a regular grammar G such that L = L (G).

The same kind of definitions are given for the context-free, context-sensitive, and recursively enumerable languages:

Definition 8. The language L is context-free, if there exists a context-free grammar G such that L = L (G).

Definition 9. The language L is context-sensitive, if there exists a context-sensitive grammar G such that L = L (G).

Definition 10. The language L is called recursively enumerable, if there exists an unrestricted grammar G such that L = L (G).

Although these are the most often described classes of the Chomsky hierarchy, there are also a number of subclasses which are worth investigating. For example, in chapter 3 we introduce the linear languages. A grammar is linear, if it is context-free, and the right hand side of its rules contain maximum one nonterminal symbol. The class of linear languages is a proper subset of the class of context-free languages, and it is a proper superset of the regular language class. Example 15. shows a typical linear language and a typical linear grammar.

Example 15. Let L be the language of the palindromes over the alphabet T = {a,b}. (Palindromes are words that read the same backward or forward.) Language L is generated by the following linear grammar.

G = ({S},{a,b},S,P)
P = {
  S → aSa,
  S → bSb,
  S → a,
  S → b,
  S → λ
}.

Language L is linear, because it can be generated by the linear grammar G.

Example 16. In Example 9 we can see a context-free grammar, which is not linear, because the production A → AA is not a linear rule. However, this context-free grammar generates a regular language, because the same language can be generated by the following regular grammar.

G = ({S,A},{0,1},S,P, and
P = {
  S → 1A,
  A → 1A,
  A → 0A,
 A → λ
}.

It is obvious that context-sensitive grammars are unrestricted as well, because each generative grammar is unrestricted. It is also obvious that regular grammars are context-free as well, because in regular grammars the left hand side of each rule is a nonterminal, which is the only condition to be satisfied for a grammar in order to be context-free.

Let us investigate the case of the context-free and context sensitive grammars.

Example 17. Let the grammar G be

G = ({S,A},{x,y},S,P)
P = {
  S → AxA,
  A → SyS,
  A → λ,
  S → λ
}.

This grammar is context-free, because the left hand side of each rule contains one nonterminal. At the same time, this grammar is not context-sensitive, because

This example shows that there are context-free grammars which are not context-sensitive. Although this statement holds for grammars, we can show that in the case of languages the Chomsky hierarchy is a real hierarchy, because each context-free language is context-sensitive as well. To prove this statement, let us consider the following theorem.

Theorem 1. For each context-free grammar G we can give context-free grammar G', which is context-sensitive as well, such that L (G) = L (G').

Proof. We give a constructive proof of this theorem. We are going to show the necessary steps to receive an equivalent context-sensitive grammar G' for a context-free grammar G = ( N, T, S, P ).

Example 18. Let the context-free grammar G be

G = ({S,A,B},{x,y},S,P)
P = {
  S → ASxB,
  S → AA,
  A → λ,
  B → SyA
}.

Now, we create a context-sensitive generative grammar G', such that L (G') = L (G).

  1. U (1) = {A},
     U (2) = {A,S} = U.
     
  2. P' = {
     S → ASxB, S → SxB, S → AxB, S → xB,
     S → AA, S → A,
     B → SyA, B → yA, B → Sy, B → y
     }.
     
  3. G' = ({S,A,B,S'},{x,y},S',P' ∪{S' → λ, S' → S}).

Exercise 6. Create a context-sensitive generative grammar G', such that L (G') = L (G)!

G = ({S,A,B,C},{a,b},S,P)
P = {
  S → aAbB,
  S → aCCb,
  C → λ,
  A → C,
  B → ACC,
  A → aSb
}.

Exercise 7. Create a context-sensitive generative grammar G', such that L (G') = L (G)!

G = ({S,X,Y},{0,1},S,P)
P = {
  S → λ,
  S → XXY,
  X → Y0Y1,
  Y → 1XS1,
  X → S00S
}.

In the following chapters we are going to investigate the language classes of the Chomsky hierarchy. We will show algorithms to decide if a word is in a language generated by a generative grammar. We will learn methods which help to specify the position of a language in the Chomsky hierarchy, and we are going to investigate the closure properties of the different language classes.

We will introduce numerous kinds of automata. Some of them accept languages, and we can use them as an alternative language definition tool, however, some of them calculate output words from the input word, and we can see them as programmable computational tools. First of all, in the next chapter, we are going to deal with the most simple class of the Chomsky hierarchy, the class of regular languages.

In order to be comprehensive we present the definition of regular grammars here again.

Definition (Regular grammars). A grammar G=(N,T,S,P) is regular if each of its productions has one of the following forms: A → u, A → uB, where A,B∈ N, u∈ T^*. The languages that can be generated by regular grammars are the regular languages (they are also called type 3 languages of the Chomsky hierarchy).

Animation 2. presents an example for a derivation in a regular grammar.

Animation 2.

We note here that the grammars and languages of the definition above are commonly referred to as right-linear grammars and languages, and regular grammars and languages are defined in a more restricted way:

Definition 12. (Alternative definition of regular grammars). A grammar G = ( N, T, S, P ) is regular if each of its productions has one of the following forms: A → a, A → aB, S → λ, where A,B ∈ N, a ∈ T. The languages that can be generated by these grammars are the regular languages.

Now we show that the two definitions are equivalent in the sense that they define the same class of languages.

Theorem 2. The language classes defined by our original definition and by the alternative definition coincide.

Proof. The proof consists of two parts: we need to show that languages generated by grammars of one definition can also be generated by grammars of the other definition.

It is clear the grammars satisfying the alternative definition satisfy our original definition at the same time, therefore, every language that can be generated by the grammars of the alternative definition can also be generated by grammars of the original definition.

Let us consider the other direction. Let a grammar G = ( N, T, S, P ) may contain rules of types A → u and A → uB (A,B ∈ N, u ∈ T^*). Then, we give a grammar G' = ( N', T, S', P' ) such that it may only contain rules of the forms A → a, A → aB, S' → λ (where A,B ∈ N', a ∈ T) and it generates the same language as G, i.e., L (G) = L (G').

First we obtain a grammar G'' such that L (G) = L (G'') and G'' = ( N'', T, S, P'' ) may contain only rules of the following forms: A → a, A → aB, A → B, A → λ (where A,B ∈ N'', a ∈ T). Let us check every rule in P: if it has one of the forms above, then we copy it to the set P'', else we will do the following:

When every rule is analyzed (and possibly replaced by a set of rules) we have grammar G''. It is clear that the set of productions P'' of G'' may contain only rules of the forms A → a, A → aB, A → a, A → λ (where A,B ∈ N'', a∈ T), since we have copied only rules from P that have these forms, and all the rules that are added to the set of productions P'' by replacing a rule are of the forms A → aB, A → a (where A,B ∈ N'', a ∈ T). Moreover, exactly the same words can be derived in G'' and in G. The derivation graphs in the two grammars can be mapped in a bijective way. When a derivation step is applied in G with a rule A → a₁... that is not in P'', then the rules must be used in G'' that are used to replace the rule A → a₁...: applying the first added rule first A → a₁X₁, then there is only one rule that can be applied in G'', since there is only one rule added with X₁ in its left hand side... therefore, one needs to apply all the rules of the chain that was used to replace the original rule A → a₁.... Then, if there is a nonterminal B at the end of the rule A → a₁..., then it is located at the end of the last applied rule of the chain, and thus the derivation can be continued in the same way in both grammars. The other way around, if we use a newly introduced rule in the derivation in G'', then we must use all the rules of the chain, and also we can use the original rule that was replaced by this chain of rules in the grammar G. In this way, there is a one-to-one correspondence in the completed derivations of the two grammars. (See Figure 2.1. for an example of replacing a long rule by a sequence of shorter rules.)

Figure 2.1. In derivations the rules with long right hand side are replaced by chains of shorter rules, resulting binary derivation trees in the new grammar.

Now we may have some rules in P'' that do not satisfy the alternative definition. The form of these rules can only be A → B and C → λ (where A,B,C ∈ N'', C ≠ S). The latter types of rules can be eliminated by the Empty-word lemma (see Theorem 1.). Therefore, we can assume that we have a grammar G''' = ( N''', T, S', P''' ) such that L (G''') = L (G) and P''' may contain only rules of the forms A → aB, A → B, A → a, S' → λ (where A,B ∈ N''', a∈ T and in case S' → λ ∈ P''' the start symbol S' does not occur on the right hand side of any of the rules of P'''). Let us define the following sets of nonterminals:

Since N''' is finite there is a minimal index k such that U_k(A) = U_k+1(A). Let U(A) denote the set U_k(A) with the above property. In this way, U(A) contains exactly those nonterminals that can be derived from A by using rules only of the form B → C (where B,C ∈ N'''). We need to replace the parts A ⇒^* B → r of the derivations in G''' by a direct derivation step in our new grammar, therefore, let G' = ( N''', T, S', P' ), where P' = {A → r∣∃ B ∈ N''' such that B → r ∈ P''', r ∉ N''' and B ∈ U(A)}. Then G' fulfills the alternative definition, moreover, it generates the same language as G''' and G.

Further we will call a grammar a regular grammar in normal form if it satisfies our alternative definitions. In these grammars the structures of the rules are more restricted: if we do not derive the empty word, then we can use only rules that have exactly one terminal in their right hand side.

Example 19. Let

{  S → 010B, 
   A → B,
   A → 2021, 
   B → 2A, 
   B → S,
   B → λ 
}). 

Give a grammar that is equivalent to G and is in normal form.

Solution:

Let us exclude first the rules that contain more than one terminal symbols. Such rules are S → 010B and A → 2021. Let us substitute them by the sets

and

of rules, respectively, where the newly introduced nonterminals are {X₁, X₂} and {X₃, X₄, X₅}, respectively. The obtained grammar is

{  S → 0X1,
   X1 → 1X2, 
   X2 → 0B,
   A → B,
   A → 2X3,
   X3 → 0X4, 
   X4 → 2X5,
   X5 → 1,
   B → 2A, 
   B → S, 
   B → λ
 ).

Now, by applying the Empty-word lemma, we can exclude rule B → λ (the empty word can be derived from the nonterminals B and A in our example) and by doing so we obtain grammar

{  S → 0X1,
   X1 → 1X2,
   X2 → 0B,
   X2 → 0,
   A → B,
   A → 2X3,
   X3 → 0X4,
   X4 → 2X5,
   X5 → 1,
   B → 2A,
   B → 2,
   B → S
}).

Now we are excluding the chain rules A → B, B → S. To do this step, first, we obtain the following sets:

Actually for those nonterminals that are not appearing in chain rules these sets are the trivial sets, e.g., U (X₁) = U₀ (X₁) = {X₁}. Thus, finally, we obtain grammar

{  S → 0X1,
   A → 0X1,
   B → 0X1,
   X1 → 1X2, 
   X2 → 0B,
   X2 → 0,
   A → 2X3,
   X3 → 0X4,
   X4 → 2X5,
   X5 → 1,
   B → 2A,
   A → 2A,
   B → 2,
   A → 2 
}).

Since our transformations preserve the generated language, every obtained grammar (G'', G''' and also G') is equivalent to G. Moreover, G' is in normal form. Thus the problem is solved.

Exercise 8. Let

{  S → abA, 
   S → A,
   A → B, 
   B → abab,
   B → aA,
   B → aaC, 
   B → λ, 
   C → aaS 
}). 

Give a grammar that is equivalent to G and is in normal form.

Exercise 9. Let

{  S → A,
   S → B,
   A → aaB,
   B → A,
   B → acS,
   B → C, 
   C → c,
   C → λ 
}). 

Give a grammar that is equivalent to G and is in normal form.

Exercise 10. Let

{  S → aA,
   S → bB,
   A → B,
   B → A,
   B → ccccC,
   B → acbcB,
   C → caacA, 
   C → cba
}). 

Give a grammar that is equivalent to G and is in normal form.

Exercise 11. Let

{  S → 11A, 
   S → 12B,
   A → B,
   B → C,
   B → 14,
   B → 4431,
   C → 3D,
   D → 233C 
}). 

Give a grammar that is equivalent to G and is in normal form.

In this section, we will describe the regular languages in another way. First, we define the syntax and the semantics of regular expressions, and then we show that they describe the same class of languages as the class that can be generated by regular grammars.

Definition 13. (Regular expressions). Let T be an alphabet and V = T ∪ {∅, λ, +, ·, ^*,(,)} be defined as its extension, such that T ∩ {∅, λ, +, ·, ^*,(,)} = ∅. Then, we define the regular expressions over T as expressions over the alphabet V in an inductive way:

Further, every regular expression can be obtained from the basic regular expressions using finite number of induction steps.

Definition 14 (Languages described by regular expressions). Let T be an alphabet. Then, we define languages described by the regular expressions over the alphabet T following their inductive definition.

The language operations used in the above definition are the regular operations:

Two regular expressions are equivalent if they describe the same language. Here are some examples:

Actually, the values of the last equivalence are frequently used, and they are denoted by r⁺, i.e., r+ ≡ rr^* by definition. This type of iteration which does not allow for 0 times iteration, i.e., only positive numbers of iterations are allowed, is usually called Kleene-plus iteration.

With the use of the above equivalences we can write most of the regular expressions in a shorter form: some of the brackets can be eliminated without causing any ambiguity in the language described. The elimination of the brackets is usually based on the associativity (both for the union and for the concatenation). Some further brackets can be eliminated by fixing a precedence order among the regular operations: the unary operation (Kleene-)star is the strongest, then the concatenation (the product), and (as usual) the union (the addition) is the weakest.

We have regular grammars to generate languages and regular expressions to describe languages, but these concepts are not independent. First we will prove one direction of the equivalence between them.

Theorem 3. Every language described by a regular expression can be generated by a regular grammar.

Proof. The proof goes by induction based on the definition of regular expressions. Let r be a basic regular expression, then

If r is not a basic regular expression then the following cases may occur:

Since every regular expression built by finitely many applications of the induction step, for any regular expression one can construct a regular grammar such that the grammar generates the language described by the expression.

QED.

When we want to have a grammar that generates the language given by a regular expression, the process can be faster, if we know that every singleton, i.e., language containing only one word, can easily be obtained by a grammar having only one nonterminal (the start symbol) and only one production that allows to generate the given word in one step.

Example 20. Let r = (cbb)^*(ab+ba) be a regular expression (that describes a language over the alphabet {a,b,c}). Give a regular grammar that generates this language.

Solution:

Let us build up r from its subexpressions. According to the above observation, the language {cbb} can be generated by the grammar

Now, let us use our induction step to obtain the grammar G_(cbb)^* that generates the language (cbb)^*: then

The languages {ab} and {ba} can be generated by grammars

and

respectively. Their union, ab+ba, then is generated by the grammar

according to our induction step.

Finally, we need the concatenation of the previous expressions (cbb)^* and (ab+ba), and it is generated by the grammar

due to our induction step. The problem is solved.

Exercise 12. Give a regular expression that describes the language containing exactly those words that contain three consecutive a's over the alphabet {a,b}.

Exercise 13. Give a regular expression that describes the language containing exactly those words that do not contain two consecutive a's (over the alphabet {a,b}).

Exercise 14. Give a regular grammar that generates the language 0^*(1+22)(2^*+00).

Exercise 15. Give a regular grammar that generates the language 0+1(1+0)^*.

Exercise 16. Give a regular grammar that generates the language (a+bb(b+(cc)^*))^*(ababa+c^*).

In this section we first define several variations of the finite automata distinguished by the properties of the transition function.

Definition 15 (Finite automata). Let A = ( Q, T, q₀, δ, F ). It is a finite automaton (recognizer), where Q is the finite set of (inner) states, T is the input (or tape) alphabet, q₀ ∈ Q is the initial state, F ⊆ Q is the set of final (or accepting) states and δ is the transition function as follows.

One can observe, that the second variation is a special case of the first one (not having λ-transitions). The third variation is a special case of the second one having sets with at most one element as images of the transition function, while the fourth case is more specific allowing sets exactly with one element.

One can imagine a finite automaton as a machine equipped with an input tape. The machine works on a discrete time scale. At every point of time the machine is in one of its states, then it reads the next letter on the tape (the letter under the reading head), or maybe nothing (in the first variations), and then, according to the transition function (depending on the actual state and the letter being read, if any) it goes to a/the next state. It may happen in some variations that there is no transition defined for the actual state and letter, then the machine gets stuck and cannot continue its run.

There are two widely used ways to present automata: by Cayley tables or by graphs. When an automaton is given by a Cayley table, then the 0th line and the 0th column of the table are reserved for the states and for the alphabet, respectively (and it is marked in the 0th element of the 0th row). In some cases it is more convenient to put the states in the 0th row, while in some cases it is a better choice to put the alphabet there. We will look at both possibilities. The initial state should be the first among the states (it is advisable to mark it by a → sign also). The final states should also be marked, they should be circled. The transition function is written into the table: the elements of the set δ(q,a) are written (if any) in the field of the column and row marked by the state q and by the letter a. In the case when λ-transitions are also allowed, then the 0th row or the column (that contains the symbols of the alphabet) should be extended by the empty word (λ) also. Then λ-transitions can also be indicated in the table.

Automata can also be defined in a graphical way: let the vertices (nodes, that are drawn as circles in this case) of a graph represent the states of the automaton (we may write the names of the states into the circles). The initial state is marked by an arrow going to it not from a node. The accepting states are marked by double circles. The labeled arcs (edges) of the graph represent the transitions of the automaton. If p ∈ δ (q,a) for some p,q ∈ Q, a ∈ T ∪ {λ}, then there is an edge from the circle representing state q to the circle representing state p and this edge is labeled by a. (Note that our graph concept is wider here than the usual digraph concept, since it allows multiple edges connecting two states, in most cases these multiple edges are drawn as normal edges having more than 1 labels.)

In this way, implicitly, the alphabet is also given by the graph (only those letters are used in the automaton which appear as labels on the edges).

In order to provide even more clarification, we present an example. We describe the same nondeterministic automaton both by a table and by a graph.

Example 21. Let an automaton be defined by the following Cayley table:

Figure 2.2. shows the graph representation of the same automaton.

Figure 2.2. The graph of the automaton of Example 21.

These automata are used to accept words, and thus, languages:

Definition 16. (Language accepted by finite automaton). Let A = (Q, T, q₀, δ, F) be an automaton and w ∈ T^* be an input word. We say that w is accepted by A if there is a run of the automaton, i.e., there is an alternating sequence q₀ t₁ q₁ ... q_k-1 t_k q_k of states and transitions, that starts with the initial state q₀, (q_i ∈ Q for every i, they are not necessarily distinct, e.g., q_i = q_j is allowed even if i ≠ j) and for every of its transition t_i of the sequence

where a₁... a_k = w, and q_k ∈ F. This run is called an accepting run.

All words that A accepts form L(A), the language accepted (or recognized) by the automaton A.

Example 22. Let A be the automaton drawn in the next animations. We show a non-accepting run of a non-deterministic automaton A (with λ-transitions) in Animation 3.

Animation 3.

However the word 1100 is accepted by A, since it has also an accepting run that is shown in Animation 4.

Animation 4.

These finite automata are also called finite-state acceptors or Rabin-Scott automata. Let us see the language class(es) that can be accepted by these automata.

Two automata are equivalent if they accept the same language.

We have defined four types of finite automata and by the definition it seems that the latter ones are more restricted than the former ones. However, it turns out that all four versions characterize the same language class:

Theorem 4. For every finite automaton there is an equivalent (completely defined) deterministic finite automaton.

Proof. The proof is constructive. Let A = (Q, T, q₀, δ, F) be a nondeterministic finite automaton (allowing λ-transitions). Let us define, first, the λ-closure of an arbitrary set q' of states.

Since Q is finite, there is a value k such that U_k (q') = U_k+1 (q'), let us denote this set by U(q'). Practically, this set contains all the states that can be reached starting from a state of q' by only λ-transitions.

Now we are ready to construct the automaton A' = (Q', T, U (q₀), δ', F'), where Q' = 2^Q, F' ⊂ Q' includes every element q' ∈ Q' such that q' ∩ F ≠ ∅. The transition function δ' is defined as follows: for any a ∈ T and q' ∈ Q'. Actually while this can be done for all subsets of Q, subsets which cannot be reached by transitions from U (q₀) by δ' can be deleted (these useless states are not needed).

One can observe that A' is a completely defined deterministic automaton. Also, every run of A has an equivalent run of A', in fact, A' simulates every possible run of A on the input at the same time. Conversely, if A' has an accepting run, then A also has at least one accepting run for the same input. Therefore, A and A' accept the same language, consequently they are equivalent.

QED

Our previous proof gives an algorithm for the ''determinization'' of any finite automaton having only states reachable from the initial state as we will see it in details in Example 23. Note that even if we deleted these useless states, the automaton may not be minimal in the sense that the same language can be accepted by a completely defined deterministic finite automaton having less number of states than our automaton.

Example 23. Let a nondeterministic automaton be defined by the following Cayley table (note that in this algorithm the rows refer to the states of the automaton and the columns to the letters of the alphabet, and in this automaton λ-transitions are allowed):

We start with the λ-closure of the initial state U (q₀) = {q₀}. This set will count as the initial state of the new automaton: let it be in the first row of the table of this new automaton. Let us see which sets of states can be obtained from this set by using the letters of the alphabet:

Let us write these two sets in the second and third row of the table. Now let us see what sets of states can be reached from these sets. First, let us see the set {q₀, q₁, q₂}.

Since this latter set is not in the table yet, it is added to the fourth row. Now let us see the set {q₂}.

Since both of these two sets are already in the table we do not need to add a new row. Finally, let us analyse the set {q₁,q₂} (that is the last row of the table).

These sets are in the table. So the table is filled. The initial state of the new deterministic automaton is {q₀}. The final states are: {q₀, q₁, q₂}, {q₂}, and {q₁, q₂}. The next table shows the resulting deterministic finite automaton:

Example 24. Animation 5. shows an example how to obtain a completely defined deterministic automaton that is equivalent to the original nondeterministic automaton.

Animation 5.

Let A = (Q, T, q₀, δ, F) be a deterministic finite automaton such that each of its states is reachable from its initial state (there are no useless states). Then we can construct the minimal deterministic finite automaton that is equivalent to A in the following way:

Let us divide the set of states into two groups obtaining the classification C₁ = {F, Q\F}. (We denote the class where state q is by C₁[q].)

Then, for i > 1 the classification C_i is obtained from C_i-1: the states p and q are in the same class by C_i if and only if they are in the same class by C_i-1 and for every a ∈ T they behave similarly: δ (p,a) and δ (q,a) are in the same class by C_i.

Set Q is finite and, therefore, there is a classification C_m such that it is the same as C_m+1.

Then, we can define the minimal completely defined deterministic automaton that is equivalent to A: its states are the groups of the classification C_m, the initial state is the group containing the initial state of the original automaton, the final states are those groups that are formed from final states of the original automaton, formally:

where δ_Cm(C_m [q], a) = C_m [δ (q,a)] for every C_m [q] ∈ C_m, a ∈ T and F_Cm = {C_m [q]∣q ∈ F}.

It may happen that there are some words w ∈ T^* that are not prefixes of any words of a regular language L. Then, the minimal completely defined deterministic automaton contains a sink state, that is the state where the word w and other words with the same property lead the automaton. When we want to have a minimal deterministic finite automaton for these languages, allowing partial (not completely defined) finite automata, then we may delete this sink state (with the transitions into it) by decreasing the number of the states by one.

Let us see yet another example. When applying the minimization algorithm it is more convenient to put the states to the 0th row of the table and the letters of the alphabet to the 0th column of the table.

Example 25. Let the deterministic automaton A be given as follows:

Give a minimal deterministic automaton that is equivalent to A.

Solution:

Before applying the algorithm we must check which states can be reached from the initial state: from q₀ one can reach the states q₀, q₂, q₁, q₃, q₅, q₄. Observe that the automaton cannot enter state q₆, therefore, this state (column) is deleted. The task is to minimize the automaton

by the algorithm. When we perform the first classification of the states C₁ = {Q₁, Q₂} by separating the accepting and non-accepting states: Q₁ = {q₂, q₄, q₅}, Q₂ = {q₀, q₁, q₃} then we have:

Then C₂ = {Q₁₁, Q₁₂, Q₂₁, Q₂₂} with Q₁₁ = {q₂, q₅}, Q₁₂ = {q₄}, Q₂₁ = {q₀, q₁}, Q₂₂ = {q₃}. Then according to this classification we have

Since C₃ = C₂ we have the solution, the minimal deterministic finite automaton equivalent to A:

We conclude this subsection by a set of exercises.

Exercise 17. Give a finite automaton that accepts the language of words that contain the consecutive substring baab over the alphabet {a,b}.

Exercise 18. Let the automaton A be given in a Cayley table as follows:

Draw the graph of A. What is the type of A (e.g., nondeterministic with allowed λ-transitions)?

Exercise 19. The graph of the automaton A is given in Figure 2.3.

Figure 2.3. The graph of the automaton of Exercise 19.

Describe A by utilizing a Cayley table. What is the type of A (e.g., deterministic with partially defined transition function)? What is the language that A recognizes?

Exercise 20. Let a nondeterministic automaton with λ-transitions, A, be defined by the following Cayley table:

Give a completely defined deterministic automaton that is equivalent to A.

Exercise 21. Let a nondeterministic automaton A be defined by the following table:

Give a completely defined deterministic automaton that accepts the same language as A.

Exercise 22. Let a nondeterministic automaton A be defined by the graph shown in Figure 2.4.

Figure 2.4. The graph of the automaton of Exercise 22.

Give a completely defined deterministic automaton that accepts the same language as A.

Exercise 23. Let the deterministic automaton A be given as follows:

Give a minimal deterministic automaton that is equivalent to A.

Exercise 24. Let the deterministic automaton A be given by the following table.

Give a minimal deterministic automaton that is equivalent to A. (Hint: check first which states can be reached from the initial state.)

Exercise 25. Let a nondeterministic automaton A be defined by the graph shown in Figure 2.5.

Figure 2.5. The graph of the automaton of Exercise 25.

Give a minimal deterministic automaton that is equivalent to A.

2.3.1. Synthesis and Analysis of Finite Automata

Now we are going to show that exactly the class of regular languages can be described with the help of the finite automata. First we show that every regular language (type 3 language) can be accepted by finite automata.

Theorem 5. Every language generated by a regular grammar is accepted by a finite automaton.

Proof. The proof is constructive. Let G = (N, T, S, P) be a regular grammar in normal form. Then, let the finite automaton

A = (Q, T, q₀, δ,F)

be defined as follows:

let Q = N ∪ {F'} (where F' ∉ N),

q₀ = S.

Let the transition function δ be defined by the elements of P: let B ∈ δ (A,a) if A → aB ∈ P; and let F' ∈ δ (A,a) if A → a ∈ P. Further, let the set of accepting states be {F'} if S →λ is not in P and let F = {F',S} if S → λ ∈ P.

One can see that the successful derivations in the grammar and the accepting runs of the automaton have a one-to-one correspondence.

QED.

Example 26. Let

G = ({S, A, B, C}, {a, b, c}, S,

{  S → abbA,
   S → baaB,
   S → λ,
   A → aS,
   A → aC,
   B → bC,
   C → aS,
   C → cc  
}) 

generating the language L(G). Give a finite automaton that accepts the language L(G).

Solution:

First we must exclude the rules containing more than 1 terminals, as we did in the proof of Theorem 2. In this way the grammar

G' =({S, A, B, C, X₁, X₂, X₃, X₄, X₅}, {a, b, c}, S,

{  S → aX1,
   X1 → bX2,
   X2 → bA,
   S → bX3,
   X3 → aX4,
   X4 → aB,
   S → λ,
   A → aS,
   A → aC,
   B → bC,
   C → aS,
   C → cX5,
   X5 → c
}) 

can be obtained. Then, we can draw the graph of automaton A as it can be seen in Figure 2.6.

Figure 2.6. The graph of the automaton of Example 26.

Now we are going to show that the class of finite automata cannot accept more languages than the class that can be described by regular expressions.

Theorem 6. Every language accepted by a finite automaton can be described by a regular expression.

Proof. The proof is constructive. We present an algorithm that shows how one can construct a regular expression from a finite automaton. We can restrict ourselves to deterministic finite automaton, since we have already seen that they are equivalent to the nondeterministic finite automata. Let the states of a deterministic finite automaton be 1,2,... for the sake of simplicity, i.e., let A = ({1,... n}, T, 1, δ, F) be given. Let denote the regular expression that describes the language accepted by the automaton ({1,...,k} ∪ {i,j}, T, i, δ', {j}), where δ' is the restriction of δ containing only transitions from the set {i} ∪ {1,...,k} to the set {1,...,k} ∪ {j} (1 ≤ i,j ≤ n, 0 ≤ k ≤ n and 1,..., 0 means the empty set).

Then, describes the regular language that is given by direct transition(s) from state i to j. Therefore, gives the language {λ} ∪ {a∣δ (i,a) = i} (this language contains the empty word and possibly some one-letter-long words, i.e., it is described by a basic regular expression or finite union of basic regular expressions).

Further, describes the language {a∣δ (i,a) = j} if i ≠ j (it can contain some one-letter-long words). These regular expressions can easily be obtained and proven to describe the languages mentioned.

Now we use induction on the upper index:

for 1 ≤ k ≤ n. This expression can be seen intuitively: starting from state i we could reach state j by using the first k states in our path, either without using state k (the part refers to this case) or by a path reaching state , and then reaching it arbitrarily many times (including 0 times: , and finally reaching state j from state

Finally, gives a regular expression that describes exactly the language accepted by A. In this way it is constructively proven that for any finite automaton one can construct a regular expression that describes the language accepted by the automaton.

QED.

Example 27. Let the Cayley table of automaton A be given as follows:

T Q	→q1	q2	q3
a	q2	q3	q1
b	q3	q2	-

Describe the accepted language L(A) by a regular expression.

Solution:

Let us describe the regular expressions for i,j ∈ {1,2,3} by using the transitions of A.

Now by using the inductive step we compute for i,j ∈ {1,2,3}.

• 

• 

• 

• 

• 

• 

• 

• 

• 

Now we can continue by computing the expressions

• 

• 

• 

• 

• 

• 

• 

• 

• 

To describe L(A) we need Let us compute it:

• 

• 

Thus, the regular expression

(ab^*a + b)(aab^*a + ab)^* aab^* + ab^* + (ab^*a + b)(aab^*a + ab)^* = (ab^*a + b)(aab^*a + ab)^* (λ + aab^*) + aab^*

describes L(A). The problem is solved.

Now we have proven that the three concepts we have discussed in this chapter, the regular grammars, regular expressions and finite automata are equivalent in the sense that each of them characterize exactly the class of regular languages (see Figure 2.7).

Figure 2.7. The equivalence of the three types of descriptions (type-3 grammars, regular expressions and finite automata) of the regular languages.

The aim of the analysis of a finite automaton is the task to describe the accepted language in another way, usually, by regular expressions. The synthesis of a finite automaton is the construction of the automaton that accepts a regular language that is usually given by a regular expression. Kleene has proven the equivalence of finite automata and regular expressions.

The minimization algorithm is very important, since the minimal, completely defined, deterministic finite automaton is (the only known) unique identification of a regular language. In this way, we can decide if two regular languages (given by regular expressions, grammars or automata) coincide or not.

We close this subsection by a set of exercises.

Exercise 26. Let

G = ({S, A, B}, {0,1}, S,

{  S → 000A,
   S → 111B,
   A → λ,
   A → 0S,
   A → 11,
   B → 1S,
   B → 000 
}) 

generating language L(G). Give a finite automaton that accepts language L(G). (Hint: first transform the grammar to normal form.)

Exercise 27. Let

G = ({S, A, B, C}, {a,b}, S,

{  S → aaaA,
   S → bbB,
   S → C,
   A → S,
   A → baB,
   A → ba,
   B → S,
   B → C,
   B → b,
   B → λ,
   C → B,
   C → aA
}) 

generating language L(G). Give a finite automaton that accepts language L(G).

Exercise 28. Let

G = ({S, A, B}, {a, b, c}, S,

{  S → abA,
   S → bccS,
   A → bS,
   A → c,
   A → B,
   B → S,
   B → aA, 
   B → bcc,
   B → λ
}) 

generating language L(G). Give a finite automaton that accepts language L(G).

Exercise 29. Let the automaton A be defined by the following table:

T Q	→q1	q2	q3
0	q1	q3	q3
1	q2	q2	q1

Give a regular expression that describes the language accepted by automaton A.

Exercise 30. Let automaton A, accepting language L(A), be defined by the Cayley table:

T Q	→q1	q2	q3
a	q1	q3	-
b	-	q2	q1
c	q2	q2	-

Give a regular expression that describes language L(A).

Exercise 31. Let automaton A be as it is shown in Figure 2.8. Give a regular expression that defines the same language as A.

Figure 2.8. The graph of the automaton of Exercise 31.

2.3.2. The Word Problem

The word problem is to decide whether any given word w belongs to a given regular language (or not). This can be done very efficiently by using a deterministic finite automaton that accepts the given language. (Such an automaton can be constructed from a regular expression, first by Theorem 3. and then/or from a grammar by Theorem 5. and then/or from a nondeterministic finite automaton by Theorem 4.) Reading the word w can be done by ∣w∣ steps, and then, if the automaton accepts w, i.e., it arrived at an accepting state in this run, then w is an element of the language. Otherwise, (if there were some undefined transitions and the automaton gets stuck, or by reading the word finally a non accepting state is reached) w does not belong to the given regular language. The decision on an input word of length n is done in at most n steps, therefore, this is a real time algorithm (i.e., linear time algorithm with coefficient 1). There is no faster algorithm that can read the input, so the word problem for regular languages can be solved very efficiently.

Exercise 32. Let automaton A be given as it can be seen in Figure 2.9.

Figure 2.9. The graph of the automaton of Exercise 32.

Decide whether the words

   abab, 
   baba, 
   aaaabbb, 
   bbbaaaab, 
   baabaabaabb and 
   aaaabbbababaaa are in L(A). 

Exercise 33. Let the nondeterministic automaton A be defined by the Cayley table:

T Q	0	1	λ
→q0	q1, q4	q5	q2
q1	q3	q1, q4	-
q2	q1	q2	-
q3	-	-	q2
q4	-	q4	-
q5	q5	q5	q0

Decide which of the words 0011, 0101, 0110, 01110010, 100, 1011110 belong to the accepted language of A.

Exercise 34. Let

G = ({S, A, B}, {a, b, c}, S,

{  S → abcS,
   S → bcA,
   S → acB,
   A → aS,
   A → a,
   B → bS,
   B → bcc,
   S → ccc
}) 

be a regular grammar. Decide which of the following words can be generated by G:

   abcccc, 
   acbcc, 
   acbbacbccc,
   bca, 
   bcacacc, 
   bcaabcacbcc, 
   ccc, 
   cccacbc.

Exercise 35. Given the regular language

a^* + (a+b)^*baba (a+b)^*),

decide if the following words are in the described language or not:

   aaaaa, 
   aaabaa, 
   ababa, 
   abbabaaba.