TOC Chapter 3

Chapter 3. Finite State Automata

A language is a subset of the set of strings over an alphabet. In Chapter 2, we have seen how a language can be generated by a grammar. A language can also be recognized by a machine. Such a device is called a recognition device. Hence, a language can have a representation in terms of a generative device as a grammar as well as in terms of a recognition device which is called an acceptor. The simplest machine or recognition device is the finite state automaton which we discuss in this chapter and in the next two chapters. Apart from these two types of representation, there are other representations like regular expressions, which is also discussed in this chapter.

Consider a man watching a TV in his room. The TV is in ‘on’ state. When it is switched off, the TV goes to ‘off’ state. When it is switched on, it again goes to ‘on’ state. This can be represented by the following Figure.

3.1. Deterministic Finite State Automaton (DFSA)

So far we have considered the finite state machine as an input/output device. We can also look at the finite state automaton (FSA) as accepting languages, i.e., sets of strings. We can look at the FSA with an input tape, a tape head, and a finite control (which denotes the state) (Figure 3.7).

Figure 3.7. FSA as a recognizer

3.2. Non-deterministic Finite State Automaton (NFSA)

In Section 3.1, we have seen what is meant by a DFSA. If the machine is in a particular state and reads an input symbol, the next state is uniquely determined. In contrast, we can also have a non-deterministic FSA (NSFA), where the machine has the choice of moving into one of a few states.

Consider the following state diagram of a NFSA (Figure 3.9).

3.3. Regular Expressions

Regular expressions are another way of specifying regular sets.

Definition 3.4 Let Σ be an alphabet. For each a in Σ, a is a regular expression representing the regular set {a}. φ is a regular expression representing the empty set. ε is a regular expression representing the set {ε}. If r1 and r2 are regular expressions representing the regular sets R1 and R2 respectively, then r1 + r2 is a regular expression representing R1 ∪ R2. r1r2 is a regular expression representing R1R2. is a regular expression representing . Any expression obtained from φ, ε, a(a ∊ Σ), using the above operations and parentheses where required, is a regular expression.

Problems and Solutions

Problem 1.	Construct DFSA for the following sets of strings. a. The set of strings over {a, b} having an even number of a’s and odd number of b’s.
Solution.	It should be noted that the set of strings over Σ = {a, b} can be divided into four classes. having even number of a’s and even number of b’s. having even number of a’s and odd number of b’s. having odd number of a’s and even number of b’s. having odd number of a’s and odd number of b’s. Strings in class (i) take the machine to q0, class (ii) to q3, class (iii) to q1, and class (iv) to q2 (Figure 3.31). Figure 3.31. Solution to Problem 1.a
b.	The set of strings over {a, b} whose length is divisible by 4 (Figure 3.32).
	Figure 3.32. Solution to Problem 1.b
c.	The set of strings over {a, b, c} having bca as substring (Figure 3.33).
	Figure 3.33. Solution to Problem 1.c
d.	The set of strings over {a, b, c} in which the substring abc occurs an even number of times (possibly zero) (Figure 3.34).
	Figure 3.34. Solution to Problem 1.d
Problem 2. a.	Describe the language accepted by the following DFSA in Figure 3.35. Figure 3.35. State diagram for Problem 2.a
Solution.	L = {(ab)n|n ≥ 0}.
b.	Describe the language accepted by the following DFSA in Figure 3.36. Figure 3.36. State diagram for Problem 2.b
Solution.	L = set of strings in (a, b)* whose length is divisible by 3.
c.	Describe the language accepted by the following DFSA in Figure 3.37. Figure 3.37. State diagram for Problem 2.c
Solution.	L = {anbmcp|n, m, p ≥ 1}.
d.	Describe the language accepted by the following DFSA in Figure 3.38. Figure 3.38. State diagram for Problem 2.d
Solution.	Set of strings over {a, b} containing aaa as a substring.
Problem 3. a.	For the following NFSA find equivalent DFSA (Figure 3.39). Figure 3.39. State table for Problem 3.a The state table can be represented by the state diagram as given below (Figure 3.40). Figure 3.40. State diagram for Problem 3.a
Solution.	Figure 3.41. Solution to Problem 3.a
b.	For the following NFSA find equivalent DFSA (Figure 3.42). Figure 3.42. State table for Problem 3.b The state table can be represented by the state diagram given in Figure 3.13.
Solution.	Figure 3.43. Solution to Problem 3.b
c.	For the following NFSA find equivalent DFSA (Figure 3.44). Figure 3.44. State table for Problem 3.c
	The state table can be represented by the state diagram given in Figure 3.12. Figure 3.45. Solution to Problem 3.c
d.	For the following NFSA find equivalent DFSA (Figure 3.46). Figure 3.46. State table for Problem 3.d The state table can be represented by the state diagram given below (Figure 3.47:). Figure 3.47. State diagram for Problem 3.d
Solution.	Figure 3.48. Solution to Problem 3.d Note The language accepted is the set of strings over {0, 1}, where the third symbol from the end is a ‘0.’ We note that the DFSA requires 23 = 8 states. In general for a language over Σ = {0, 1}, if the nth element from the end is fixed, we can have a NFSA with n + 1 states, but the DFSA requires 2n states.
Problem 4.	Write regular expression for each of the following languages over the alphabet {a, b}. The set of strings containing ab as a substring. The set of strings having at most one pair of consecutive a’s and at most one pair of consecutive b’s. The set of strings whose length is divisible by 6. The set of strings whose 5th last symbol (5th symbol from the end) is b.
Solution.	A = (a + b)*ab(a + b)* One pair of a’s but no pair of b’s B1 = (b + ε)(ab)*aa(ba)*(b + ε) One pair of b’s but no pair of a’s B2 = (a + ε)(ba)*bb(ab)*(a + ε) B = B1 + B2 aa occurring before bb C = (b + ε)(ab)* aa(ba)* bb(ab)* (a + ε) bb occurring before aa D = (a + ε)(ba)* bb(ab)* aa(ba)* (b + ε) No pair of a’s and b’s E = (b + ε)(ab)* (a + ε) Required regular expression is B + C + D + E [(a + b)6]* (a + b)*b(a + b)4

Exercises

1.	The following are the state diagrams of two DFSA’s M1 and M2. Answer the following questions about these machines (Figure 3.49) Figure 3.49. State diagrams for Exercise 1 What is the start state of M1? What are the accepting states of M1? What is the start state of M2? What is the sequence of states does M1 go through on input 0000111? Does. M1 accept 00001111? Does M2 accept ε?
2.	Construct DFSA to accept the following languages. {a, b}+ {a, b}* {(ab)n|n ≥ 1} {anbmcp|n, m, p ≥ 1} {w|w ∊ {a, b}*, w has an even number of a’s and even number of b’s}
3.	Find a DFSA for each of the following languages. L = {w|w is a binary string containing both substrings 010 and 101}. For any fixed integer k ≥ 0, L = {0iw1i|w is a binary string and 0 ≤ i ≤ k}.
4.	Suppose we restrict DFSA’s so that they have at most one accepting state. Can any regular language L be recognized by this restricted form of DFSA? Justify your answer.
5.	Design deterministic finite automata for each of the following sets: the set of all strings in {1, 2, 3}* containing 231 as substring. the set of strings x ∊ {0, 1}* such that #0(x) is even and #1 (x) is a multiple of three. the set of strings in (a)* whose length is divisible by either 2 or 7.
6.	Let Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Consider the base 10 numbers formed by strings from Σ*. 15 represents fifteen, 408 represents four hundred, and eight and so on. Let L = {x ∊ Σ*| the numbers represented by x is exactly divisible by 7} = {∊, 0, 00, 000,..., 7, 07, 007,..., 14, 21, 28, 35,...}. Find a DFSA that accepts L.
7.	Let Σ = {a, b}. Consider the language consisting of all words that have neither consecutive a’s nor consecutive b’s. Draw a DFSA that accepts this language.
8.	Let Σ = {a, b, c}. Let L = {x ∊ {a, b, c}*||x| = 0 mod 5}. Draw a DFSA that accepts L.
9.	Let Σ = {a, b, c}. Consider the language consisting of words that begin and end with different letters. Draw a DFSA that accepts this language.
10.	Let Σ = {a, b, c}. Draw a DFSA that rejects all words for which the last two letters match. Draw a DFSA that rejects all words for which the first two letters match.
11.	Suppose we alter the definition of a DFSA so that once the automaton leaves its start state, it cannot return to its start state. For such a DFSA, if an input w causes it to take a transition from a state p to its start state q0, where p ≠ q0, then the DFSA immediately halts and rejects w. Call this new type of DFSA as no-return-DFSA. Prove that the class of languages recognized by no-return-DFSA is the class of regular languages.
12.	Construct a NFSA for each of the languages given in problem no. 1,3,5,6,7,8,9.
13.	Given a non-deterministic finite automaton M without ε-transitions, show that it is possible to construct a NFSA with ε-transitions M′ such that: M′ has exactly one start state and one end state L(M) = L(M′).
14.	What is the language accepted by the NFSA M (Figure 3.50)? Figure 3.50. State diagram for Exercise 14
15.	Let Σ = {a, b}. Find a NFSA for each of the following languages: {x|x contains an even number of a’s}. {x|x contains an odd number of b’s}. {x|x contains an even number of a’s and an odd number of b’s} {x|x contains an even number of a’s or an odd number of b’s}
16.	Suppose we alter the definition of an NFSA so that we now identify two types of states in its state set Q: the good states G ⊆ Q, and the bad states B ⊆ Q where G ∩ B = φ. (Note that a state in Q may be neither good nor bad, but no state is both good and bad). The automata accepts input w if, considering all possible computations on w, some computation ends in G and no computation ends in B. Call this new type of NFSA as a good-bad NFSA. Prove that the class of languages recognized by good-bad NFSAs is the class of regular languages.
17.	In the questions below, given a language L we describe how to form a new language from the strings in L. Prove that if L is regular then the new languages are regular by constructing an NFSA for the new languages. skip(L) = {xy|xcy ∊ L, where x and y are strings, c is a letter} suffix(L) = {y|xy ∊ L, x, y are strings}.
18.	Convert the following two NFSA to equivalent DFSA using subset construction method (Figure 3.51). Figure 3.51. State diagrams for Exercise 18
19.	Prove the following identities for regular expressions r, s and t. Here r = s means L(r) = L(s). r + s = s + r φ* = ε (r*s*)* = (r + s)* (rs)* r = r(sr)*
20.	Construct a NFSA accepting the language denoted by the following regular expressions. Also convert the NFSA to an equivalent DFSA. a*ba*ab* a*bb*(a + b)ab* b((aab* + a4)b)*a
21.	Given the following DFSAs, construct equivalent regular expressions (Figure 3.52). Figure 3.52. State diagrams for Exercise 21
22.	Give an NFSA with four states equivalent to the regular expression (01 + 011 + 0111)*. Convert this automaton to an equivalent DFSA using subset construction.
23.	Give regular expressions that describe each of the following languages, which are over the alphabet {0, 1}. Explain how you constructed your regular expressions. {w| w contains substrings 010 and 101} {w|w does not contain substring 0110} {w| w has an even number of 0’s and an even number of 1’s} {w|w has the same number of occurrences of 10 and 01} Note that in (a) and (d) occurrences can overlap.
24.	For each of the following languages, give two strings that are members and two strings that are not members – a total of four strings for each part. Let Σ = {a, b} in all parts. a*b* a(ba)*b a* ∪ b* (aaa)* Σ*aΣ*bΣ*aΣ* aba ∪ bab (Σ ∪ a)b (a ∪ ba ∪ bb) Σ*
25.	Let Σ = {a, b}. Give (if possible) a regular expression that describes the set of all even-length words in Σ*.
26.	Give examples of sets that demonstrate the following inequalities. Here, r1, r2, r3 are regular expressions. r1 + ∊ ≠ r1 r1 · r2 ≠ r2 · r1 r1 · r1 ≠ r1 r1 + (r2 · r3) ≠ (r1 + r2) · (r1 + r3) (r1 · r2)* ≠ (r*1 · r*2)*
27.	Find examples of sets that show the following expressions maybe equal under some conditions. Here, r1, r2, r3 are regular expressions. r1 + ∊ = r1 r1 · r2 = r2 · r1 (even if r1 ≠ r2) r1 · r1 = r1 r1 + (r2 · r3) = (r1 + r2) · (r1 + r3) (even if r1 ≠ r2 and r3 = r1)
28.	Solve the following language equations for X1, X2, and X3 by eliminating X3 and then eliminating X2. Solve for X1 and then back-substitute to find X2 and X3. X1 = φ + φX1 + (0 + 1)X2 + φX3 X2 = ∊ + 0X1 + 1X2 + φX3 X3 = φ + φX1 + (0 + 1) X2 + φX3.