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 bb, bc, 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 |