Introduction to Automata Theory, Languages, and Computation |

A | B | |
---|---|---|

->000r | 100r | 011r |

*000a | 100r | 011r |

*001a | 101r | 000a |

010r | 110r | 001a |

*010a | 110r | 001a |

011r | 111r | 010a |

100r | 010r | 111r |

*100a | 010r | 111r |

101r | 011r | 100a |

*101a | 011r | 100a |

110r | 000a | 101a |

*110a | 000a | 101a |

111r | 001a | 110a |

Basis: If *y = epsilon*, then the statement is *dhat(q,x) =
dhat(dhat(q,x),epsilon)*.
This statement follows from the basis in the definition of *dhat*.
Note that in applying this definition, we must treat *dhat(q,x)* as
if it were just a state, say *p*.
Then, the statement to be proved is *p = dhat(p,epsilon)*, which is
easy to recognize as the basis in the definition of *dhat*.

Induction:
Assume the statement for strings shorter than *y*, and break *y =
za*, where *a* is the last symbol of *y*.
The steps converting *dhat(dhat(q,x),y)* to *dhat(q,xy)* are
summarized in the following table:

Expression | Reason |
---|---|

dhat(dhat(q,x),y) | Start |

dhat(dhat(q,x),za) | y=za by assumption |

delta(dhat(dhat(q,x),z),a) | Definition of dhat,
treating dhat(q,x) as a state |

delta(dhat(q,xz),a) | Inductive hypothesis |

dhat(q,xza) | Definition of dhat |

dhat(q,xy) | y=za |

0 | 1 | |
---|---|---|

->A | B | A |

B | C | A |

*C | C | A |

The table below shows this automaton.
State *qi* means that the input seen so far has remainder *i*
when divided by 5.

0 | 1 | |
---|---|---|

->*q0 | q0 | q1 |

q1 | q2 | q3 |

q2 | q4 | q0 |

q3 | q1 | q2 |

q4 | q3 | q4 |

There is a small matter, however, that this automaton accepts strings
with leading 0's.
Since the problem calls for accepting only those strings that begin with
1, we need an additional state *s*, the start state, and an
additional ``dead state'' *d*.
If, in state *s*, we see a 1 first, we act like *q0*; i.e., we
go to state *q1*.
However, if the first input is 0, we should never accept, so we go to
state *d*, which we never leave.
The complete automaton is:

0 | 1 | |
---|---|---|

->s | d | q1 |

*q0 | q0 | q1 |

q1 | q2 | q3 |

q2 | q4 | q0 |

q3 | q1 | q2 |

q4 | q3 | q4 |

d | d | d |

Basis: *|w|* = 1.
Then *dhat(q_0,w) = dhat(q_f,w)*, because *w* is a single
symbol, and *dhat* agrees with *delta* on single symbols.

Induction:
Let *w = za*, so the inductive hypothesis applies to *z*.
Then *dhat(q_0,w) = dhat(q_0,za) = delta(dhat(q_0,z),a) =
delta(dhat(q_f,z),a)* [by the inductive hypothesis] = *dhat(q_f,za) =
dhat(q_f,w)*.

For part (b), we know that *dhat(q_0,x) = q_f*.
Since *xepsilon*, we know by part (a) that
*dhat(q_f,x) = q_f*.
It is then a simple induction on *k* to show that *dhat(q_0,x^k)
= q_f*.

Basis:
For *k=1* the statement is given.

Induction:
Assume the statement for *k-1*; i.e., *dhat(q_0,x^{k-1}) =
q_f*.
Using Exercise 2.2.2, *dhat(q_0,x^k) = dhat(dhat(q_0,x^{k-1}),x) =
dhat(q_f,x)* [by the inductive hypothesis] = *q_f* [by (a)].

Basis:
*|w|* = 0.
Then *w*, the empty string surely has an even number of 1's, namely
zero 1's, and *dhat(A,w) = A*.

Induction:
Assume the statement for strings shorter than *w*.
Then *w = za*, where *a* is either 0 or 1.

Case 1: *a* = 0.
If *w* has an even number of 1's, so does *z*.
By the inductive hypothesis, *dhat(A,z) = A*.
The transitions of the DFA tell us *dhat(A,w) = A*.
If *w* has an odd number of 1's, then so does *z*.
By the inductive hypothesis, *dhat(A,z) = B*, and
the transitions of the DFA tell us *dhat(A,w) = B*.
Thus, in this case, *dhat(A,w) = A* if and only if *w* has an
even number of 1's.

Case 2: *a* = 1.
If *w* has an even number of 1's, then *z* has an odd number
of 1's.
By the inductive hypothesis, *dhat(A,z) = B*.
The transitions of the DFA tell us *dhat(A,w) = A*.
If *w* has an odd number of 1's, then *z* has an even number
of 1's.
By the inductive hypothesis, *dhat(A,z) = A*, and
the transitions of the DFA tell us *dhat(A,w) = B*.
Thus, in this case as well, *dhat(A,w) = A* if and only if *w* has an
even number of 1's.

0 | 1 | |
---|---|---|

->A | B | A |

B | D | C |

C | E | A |

D | F | C |

*E | F | G |

*F | F | G |

*G | E | H |

*H | E | H |

0 | 1 | ... | 9 | |
---|---|---|---|---|

->qs | {qs,q0} | {qs,q1} | ... | {qs,q9} |

q0 | {qf} | {q0} | ... | {q0} |

q1 | {q1} | {qf} | ... | {q1} |

... | ... | ... | ... | ... |

q9 | {q9} | {q9} | ... | {qf} |

*qf | {} | {} | ... | {} |

a | b | c | d | |
---|---|---|---|---|

->q0 | {q0,q1,q4,q7} | {q0} | {q0} | {q0} |

q1 | {} | {q2} | {} | {} |

q2 | {} | {} | {q3} | {} |

*q3 | {} | {} | {} | {} |

q4 | {} | {q5} | {} | {} |

q5 | {} | {} | {} | {q6} |

*q6 | {} | {} | {} | {} |

q7 | {q8} | {} | {} | {} |

q8 | {} | {} | {q9} | {} |

q9 | {} | {} | {} | {q10} |

*q10 | {} | {} | {} | {} |

a | b | c | d | |
---|---|---|---|---|

->A | B | A | A | A |

B | C | D | A | A |

C | C | D | E | A |

D | B | A | F | G |

E | B | A | A | H |

*F | B | A | A | A |

*G | B | A | A | A |

*H | B | A | A | A |

For (b), begin by noticing that *a* always leaves the state unchanged.
Thus, we can think of the effect of strings of *b*'s and *c*'s only.
To begin, notice that the only ways to get from *p* to *r* for the first
time, using only *b*, *c*, and epsilon-transitions are *b**b*, *b**c*,
and *c*.
After getting to *r*, we can return to *r* reading either *b* or *c*.
Thus, every string of length 3 or less, consisting of *b*'s and
*c*'s only, is accepted, with the exception of the string *b*.
However, we have to allow *a*'s as well.
When we try to insert *a*'s in these strings, yet keeping the length to
3 or less, we find that every string of *a*'s *b*'s, and *c*'s with at
most one *a* is accepted.
Also, the strings consisting of one *c* and up to 2 *a*'s are accepted;
other strings are rejected.

There are three DFA states accessible from the initial state, which is
the epsilon closure of *p*, or *{p}*.
Let *A = {p}, B = {p,q}*, and *C = {p,q,r}*.
Then the transition table is:

a | b | c | |
---|---|---|---|

->A | A | B | C |

B | B | C | C |

*C | C | C | C |