CS 341 Homework 8
Finite Automata, Regular Expressions, and Regular Grammars
1. We showed that the set of finite state machines is closed under complement. To do that, we presented a technique for converting a deterministic machine M into a machine M' such that L(M') is the complement of L(M). Why did we insist that M be deterministic? What happens if we interchange the final and nonfinal states of a nondeterministic finite automaton?
2. Give a direct construction for the closure under intersection of the languages accepted by finite automata. (Hint: Consider an automaton whose set of states is the Cartesian product of the sets of states of the two original automata.) Which of the two constructions, the one given in the text or the one suggested in this problem, is more efficient when the two languages are given in terms of nondeterministic finite automata?
3. Using the either of the construction techniques that we discussed, construct a finite automaton that accepts the language defined by the regular expression: a*(ab ba )b*.
4. Write a regular expression for the language recognized by the following FSM:
a
b
b a
a
a,b
b
5. Consider the following FSM M:
0a 1b 3
b a b
2
(a) Write a regular expression for the language accepted by M.
(b) Give a deterministic FSM that accepts the complement of the language accepted by M.
6. Construct a deterministic FSM to accept each of the following languages:
(a) (aba aabaa)*
(b) (ab)*(aab)*
7. Consider the language L = {w (a, b)* : w has an odd number of a's}
(a) Write a regular grammar for L.
(b) Use that grammar to derive a (possibly nondeterministic) FSA to accept L.
8. Construct a deterministic FSM to accept the intersection of the languages accepted by the following FSMs:
a 2 ab 2' b
b a
1b1' a
b a
3 a 3' b
9. Consider the following FSM M:
a
a b
1 b2 a3 b4 a,b
(a) Give a regular expression forL(M).
(b) Describe L(M) in English.
Solutions
1. We define acceptance for a NDFSA corresponding to the language L as there existing at least one path that gets us to a final state. There can be many other paths that don't, but we ignore them. So, for example, we might accept a string S that gets us to three different states, one of which accepts (which is why we accept the string) and two of which don't (but we don't care). If we simply flip accepting and nonaccepting states to get a machine that represents the complement of L, then we still have to follow all possible paths, so that same string S will get us to one nonaccepting state (the old accepting state), and two accepting states (the two states that previously were nonaccepting but we ignored). Unfortunately, we could ignore the superfluous nonaccepting paths in the machine for L, but now that those same paths have gotten us to accepting states, we can't ignore them, and we'll have to accept S. In other words, we'll accept S as being in the complement of L, even though we also accepted it as being in L. The key is that in a deterministic FSA, a rejecting path actually means reject. Thus it makes sense to flip it and accept if we want the complement of L. In a NDFSA, a rejecting path doesn't actually mean reject. So it doesn't make sense to flip it to an accepting state to accept the complement of L.
2.
4. Without using the algorithm for finding a regular expression from an FSM, we can note in this case that the lower right state is a dead state, i.e., an absorbing, non-accepting state. We can leave and return to the initial state, the only accepting state, by reading ab along the upper path or by reading ba along the lower path. These can be read any number of times, in any order, so the regular expression is (ab ba)*. Note that is included, as it should be.
5. (a) ((a ba)(ba)*b)
(b)
a
{1}{2, 3}
a b
{0} a b
a
b
{2} a,b
b
6. (a)
a
a a
b ba,b
a b
b
a
a,b
b
(b) a
a a
b
b a b b
a
a,bb
7. (a) Nonterminal S is the starting symbol. We'll use it to generate an odd number of a's. We'll also use the nonterminal E, and it will always generate an even number of a's. So, whenever we generate an a, we must either stop then, or we must generate the nonterminal E to reflect the fact that if we generate any more a's, we must generate an even number of them.
S a b
S aE (b) a
S bS
E b S a E
E bE b
E aS a b
#
8.
b bb
<1, 1'<2, 1'<3, 1'>
a a a
b b
<1, 2'<2,2'<3, 2'>
a a a
b b
<1,3'<2, 3'<3, 3'>
aa
b
b
a
9. (a) (a bb*aa)* ( bb*(a ))
(b) All strings in {a, b}* that contain no occurrence of bab.
Homework 8 Finite Automata, Regular Expressions, and Regular Grammars 1