Solutions (or Hints) to Chapter-end Exercises i;; 385
3.14 Jr/s are given below:
JrQ = {{q6}, {qQ, q), q2' q3' q4. q5}}
Jr, = {{q6}, {qQ, qlo q2, q3, q5}, {q4}}
Teo = {{qd, {q4}, {qQ, ql, q3}, {q2. q5}}
Jr3 = {{q6}, {q4}, {qd, {qd, {Q3}, {q2' q5}}
Jr4 = {{qd, {Q4}, {qQ}, {qd, {q3}, (q2}, {q5}}
Here Jr = Q. The minimum state automaton is simply the gIven
automaton.
3.16
Chapter 4
4.1 (a) 5 ~ 0
11 51
11 ~ O"O
Il1 A 1
111 1", n 2:: 0, m 2:: 1.
A ~ lkA =:} lk+l, k 2:: 0.
0
111 1" E L(G) when n > 111 2:: 1. So L(G) = {Oil/I" : n > m 2:: I}
(b) L(G) = {0
1l1 1" 1 Tn -:,t n and at least one of 111 and n 2:: I}. Clearly,
0
111 E L(G) and I" E L(G), where Tn, n 2:: 1.
For Tn > n, 5 ~ OIlSI Il =:} OIlOAl" ~ 0"00 " 1-111 1" = 01i/1/. Thus
0
111 1" E L(G).
(c) L(G) = {Oil 1
11 0
11
1 n 2:: I}. The proof is similar to that of
Example 4.10.
(d) L(G) = {O" 1
111 0
111 III 1 Tn, n 2:: I}.
For Tn, n 2:: 1,
5 ~ 01l-IS1,,-1 =:} 0
11
- ' OA 11
11 -
1 =:} 01l111l-1AO
I1l -
1 1 1l - 1 =:} 01l1
111 0
lil 1 1l
So,
{Oil 1
111 0
111 1
11
I111, n 2:: I} <;;;; L(G).
It is easy to prove the other inclusion.
(e) L(G) = {x E to, I t I x does not contain two consecutive O's}
4.2 (a) G = ({S, A, B}, to, I}, P, S), where P consists of 5 ---'t OB IIA,
A ---'t 0!05!lAA, B ---'t 111510BB.
Prove by induction on 1 wi, W E L*, that
(i) 5 ~ W if and only if w consists of an equal number of O's and l's
Oi) A ~ w if and only if lV has one more °than it has l' s.
(iii) B ~ lV if and only if w has one more 1 than it has D's.
A =:} 0, B =:} 1 and 5 does not derive any terminal string of length one.