TOC Chapter 4

Chapter 4. Finite State Automata: Characterization, Properties, and Decidability

In this chapter, the equivalence between right linear grammars and finite state automata (FSA) is proved. The pumping lemma for regular sets is considered, and is used to give a method for showing a language not to be regular. We also consider some basic closure properties and decidability results.

Regular Grammars

Theorem 4.1 If a language L is accepted by a finite non-deterministic automaton, then L can be accepted by a right linear grammar and conversely. Proof Let L be a language accepted by a finite non-deterministic automaton M = (K, Σ, δ, q0, F) where K = {q0, . . ., qn}. If w ∊ L, then w is obtained by the concatenation of symbols corresponding to different transitions starting from q0 and ending at a finite state. Hence, for each transition by M while reading a symbol of w, there must be a correspondence to a production of a right linear grammar G. The construction is as shown below: G = ({S0, S1, . . ., Sn}, Σ, P, S0) where productions in P are Si → aSj if δ(qi, a) contains qj for qj ∉ F Si → aSj and Si → a if δ(qi, a) contains qj, qj ∊ F. To prove L(G) = L = L(M). From the construction of P, one is able to see that Si ⇒ aSj, if and only if δ(qi, a) contains qj and Si ⇒ a, if and only if δ(qi, a) ∊ F. Hence, if S0 ⇒ a1S1 ⇒ a1a2S2 ⇒ . . . ⇒ a1 . . . an if and only if δ(q0, a1) contains q1, δ(q1, a2) contains q2, . . ., δ(qn-1, an) contains qn where qn ∊ F. Hence, w ∊ L(G) if and only if w ∊ L(M). Let G = (N, T, P, S) be a right linear grammar. An equivalent non-deterministic finite state automaton (NFSA) with ε-moves is constructed as below: Let M = (K, T, δ, [S], [ε]), where K = {[α]|α is S or suffix of some right-hand side of a production in P, the suffix need not be proper}. The transition function δ is defined as follows: δ([A], ε) = {[α]|A → α ∊ P} If a ∊ T or α ∊ T*N, then δ([aα], a) = {[α]}. Clearly, [α] ∊ δ([S], w) if and only if where A → yα ∊ P and xy = w. If w ∊ L(M), then α = ε. M accepts w if and only if . Hence the converse follows.

4.2. Pumping Lemma for Regular Sets

A language is said to be regular, if it is accepted either by a finite automaton or it has a regular grammar generating it. In order to prove that a language is not regular the most commonly used technique is “pumping lemma.” The lemma gives a pumping property that a sufficiently long word has a subword (non-empty) that can be pumped. But the fact that a language satisfies pumping lemma does not mean that it is regular.

4.3. Closure Properties

Theorem 4.3 The family of regular languages is closed under the following operations: (1) union (2) intersection (3) complementation (4) catenation (5) star, and (6) reversal. Proof The six closure properties will be proved below either through finite automaton or regular grammars and it has been shown that they are equivalent in Theorem 4.1.1. Union: Let L1 and L2 be two regular languages generated by two right linear grammars G1 = (N1, T1, P1, S1) and G2 = (N2, T2, P2, S2) (say). Without loss of generality let N1 ∩ N2 = φ. L1 ∪ L2 is generated by the right linear grammar. G′ = (N1 ∪ N2∪{S}, T1 ∪ T2, P1∪P2∪{S → S1, S → S2}, S). L(G′) = L(G1)∪L(G2) because, the new start symbol of G′ is S from which we reach S1 or S2 using the rules S → S1, S → S2. After this step one can use only rules from P1 or P2, hence deriving words in L1 or L2 or in both. Intersection: Let L1, L2 be any two regular languages accepted by two DFSA’s M1 = (K1, Σ1, δ1, q1, F1) and M2 = (K2, Σ2, δ2, q2, F2). Then, the DFSA M constructed as below accepts L1 ∩ L2. Let M = (K, Σ, δ, q0, F) where K = K1 × K2, q0 = (q1, q2), F = F1 × F2, δ: K × Σ → K is defined by δ((p1, p2), a) = (δ1(p1, a), δ2(p2, a)). One can see that for each input word w, M runs M1 and M2 parallely, starting from q1, q2, respectively. Having finished reading the input, M accepts only if both M1, M2 accept. Hence, L(M) = L(M1) ∩ L(M2). Complementation: Let L1 be a regular language accepted by DFSA M = (K, Σ, δ, q0, F). Then, clearly the complement of L is accepted by the DFSA Mc = (K, Σ, δ, q0, K − F). Concatenation: We prove this property using the concept of regular grammar. Let L1 and L2 and G1 and G2 be defined as in proof of union of this theorem. Then, the type 3 grammar G constructed as below satisfies the requirement that L(G) = L(G1). L(G2). G = (N1 ∪ N2, T1 ∪ T2, S1, P2 ∪ P) where P = {A → aB/A → aB ∊ P1} ∪ {A → aS2|A → a ∊ P1}. Clearly, L(G) = L(G1). L(G2) because any derivation starting from S1 derives a word w ∊ L1 and for G, . Hence, if by G2, then by G. Catenation closure: Here also we prove the closure using regular grammar. Let L1 be a regular grammar generated by G1 = (N1, T1, P1, S1). Then, the type 3 grammar G = (N1∪{S0}, T1, S0, {S0 → ε, S0 → S1} ∪ {A → aS1|A → a ∊ P1} ∪ P1). Clearly, G generates . Reversal: The proof is given using the NFSA model. Let L be a language accepted by a NFSA with ε-transitions which has exactly one final state. (Exercise: For any NFSA, there exists an equivalent NFSA with ε-transitions with exactly one final state). Let it be M = (K, Σ, δ, q0, {qf}). Then, the reversal automaton M′ = (K, Σ, δ′, qf, {q0}) where δ′ is defined as δ′(q, a) contains p, if δ(p, a) contains q for any p, q ∊ K, a ∊ Σ ∪ {ε}. One can see that if w ∊ L(M) then wR ∊ L(M′) as in the modified automaton M′, each transition takes a backward movement on w.

We prove that regular languages are also closed under homomorphism and right quotient.

4.4. Decidability Theorems

In this section, we address the basic decidability issues for regular languages. They are membership problem, emptiness problem, and equivalence problems.

Theorem 4.7 Given a regular language L over T and w ∊ T*, there exists an algorithm for determining whether or not w is in L. Proof Let L be accepted by a DFSA M (say). Then, for input w one can see whether w is accepted by M or not. The complexity of this algorithm is O(n) where |w| = n. Hence, membership problem for regular sets can be solved in linear time.

Problems and Solutions

1.	Let Σ be an alphabet. Define IΣ to be the collection of all infinite languages over Σ. Note that IΣ does not include any finite language over Σ. Prove or give counter examples to the following: IΣ is closed under union IΣ is closed under intersection
Solution.	IΣ is closed under union. Let L1 and L2 be in IΣ. L1 and L2 are infinite sets L1 ∪ L2 = {x|x ∊ L1 or x ∊ L2}. L1 ∪ L2 includes L1 and also L2. Hence L1 ∪ L2 is infinite. IΣ is not closed under intersection. Consider Σ = {a}. L1 = {a2n|n ≥ 1} is an infinite set. L2 = {ap|p is a prime} is an infinite set. L1, L2 ∊ IΣ L1 ∩ L2 = {a2} which is a finite set and hence it is not in IΣ.
2.	Construct regular grammar equivalent to the following NFSA (Figure 4.2). Figure 4.2. State diagram for Problem 2
Solution.	Let G = (N, T, P, S) where N = {S0, S1, S2}, T = {0, 1}. P consists of the following rules: S0 → 0S1, S1 → 0S2|0S0|0, S2 → 1S1|1S2|1.
3.	Construct an equivalent NFSA for the following grammar S → abS|a.
Solution.	Figure 4.3. Solution to Problem 3

Exercises

1.	Let Σ be an alphabet. Define IΣ to be the collection of all infinite languages over Σ. Note that IΣ does not include any finite language over Σ. Prove or give counter examples to the following: IΣ is closed under complementation IΣ is closed under concatenation IΣ is closed under Kleene closure
2.	If a collection of languages is closed under intersection, does it mean that it is closed under union. Prove or give counter example.
3.	If L is accepted by a NFSA, is it necessarily true that all subsets of L are accepted by a NFSA? Prove or give counter examples.
4.	Let NΣ denote the collection of languages such that no L ∊ NΣ is accepted by a NFSA. Prove or give counter examples to the following: NΣ is closed under union NΣ is closed under catenation NΣ is closed under Kleene closure
5.	We have shown that the union of two regular languages is regular. Is the union of a collection of regular languages always regular? Justify your answer.
6.	Let M be a DFSA accepting L1 and G be a regular grammar generating L2. Using only M and G show that L1 ∩ L2 is regular.
7.	Let P = {x| |x| is prime} and let I(L) be defined by I(L) = L ∩ P. Let DΣ denote the collection of all languages recognized by a DFSA Show that DΣ is not closed under I Prove or disprove NΣ is closed under I
8.	Given any alphabet Σ and a DFSA M, show that it is decidable whether M accepts even length strings.
9.	Given any alphabet Σ and regular expressions r1 and r2 over Σ, show that it is decidable whether r1 and r2 describe any common strings.
10.	Given any alphabet Σ and a regular expression r1 over Σ, show that it is decidable whether there is a DFSA with less than 31 states that accepts the language described by r1.
11.	Give a regular grammar for: (a + b)c*(d + (ab)*) (a + b)*a(a + b)*
12.	Construct a regular grammar equivalent to each of the following NFSA (Figure 4.4). Figure 4.4. State diagrams for Exercise 12
13.	Construct an equivalent NFSA for each of the following grammars: S → abS1 S1 → abS1|S2 S2 → a S → abA A → baB B → aA|bb