NO CODING ALLOWED ONLY PROOFS Use induction over the size of

NO CODING ALLOWED, ONLY PROOFS

Use induction over the size of strings to prove that the following NFA over the alphabet Sigma = {a, b} recognizes the regular language sigma *ab (that is, it accepts all w sigma * that end with ab).

Solution

We use mutual induction on the three states and their properties. The induction hypothesis is given by H(n) = for all strings w of length n, the following three statements are true.

1) q1 (q1,w) ;

2) q2 (q1,w) w ends with a ; and

3) q3 (q1,w) w ends with ab.

To prove these statements, we will have to consider how the NFA can reach each state. Also note that if the machine is to accept a string x, then (q1, x) must contain q3 as q3 is the only accepting state. Thus, proof of the third clause in the induction hypothesis, for w of arbitrary length, will prove that the NFA accepts only those strings ending in ab.

Basis: H(0)

Since |w|0, we know that w=. Because q1 is the start state of the NFA, and there are no -transitions out of q1, (q1, ) = {q1}. Hence, statement 1 holds.

Statement 2 also holds, because does not end in a, and q2 (q1, ), so both sides of statement 2 are false.

Similarly, q3 (q1, ), and does not end in ab, so Statement 3 holds, because both sides are false.

Induction: H(n) H(n + 1)

Assume that w=x m, where m is a symbol which is either a or b, and |x|= n. Thus, the induction hypothesis holds for x and our task is to prove it for w, since |w|= n+1.

1. q1 (q1, xm). The induction hypothesis clause 1 tells us that q1 (q1,x). m is either a or b, and transitions on both a and b go from q1 to q1. Thus statement 1 is proved.

2. If m= a, the rhs of statement 2 is true. Using statement 1, we know that q1 (q1, x). Since there is a transition on a from q1 to q2, we know that q2 (q1, xm), and the lhs is also true.

If m= b, the rhs of statement 2 is false. Thus we have to show that q2 (q1,xm). This is clearly the case, since the only transition into q2 is labeled with a.

3. We prove this equivalence in two parts.

[] Suppose w ends in ab. So if w=xm, m=b and x ends in a. By statement 2 applied to x, q2 (q1, x). Since ’(q2, b) = {q3}, (q1, w) = (q1, xb) = ’((q1, x), b) contains q3.

[] Suppose (q1, w) contains q3. From the diagram, it is evident that the only way to get to q3 is for w to be of the form xb, where q2 (q1, x). By statement 2 applied to x, we know that x ends in a. Thus w ends in ab.

Thus statement 3 is proved.

Notice that we needed only the third statement in the induction hypothesis to prove that the NFA accepts only those strings ending in ab. However, in the proof of statement 3 (for w of length n+1) we needed to assume statement 2 (for w of length n). Moreover, in the proof of statement 2, we needed to assume statement 1. This is why we needed all three parts of the induction hypothesis.