Use induction over the size of strings to prove that the fol

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). For all strings w E* there exists a computational path that terminates in the state q_1 (terminates without \"dying\" in the middle of computation process). For all strings w E*a (i.e., all strings that end with an a) there exists a computational path that terminates in the state q_2. For all strings w sigma*ab there exists a computational path that terminates in the state q_3. Note that due to item (3) this statement implies that the language of the above NFA is sigma*ab. In the base case you need to show that the statements holds for strings of size 0 and 1. As for the induction step, you need to show that the above induction hypothesis holds for all strings of size n greaterthanorequalto 2, assuming that it holds for all strings of size smaller than n. To do that for any string w of size n greaterthanorequalto 2 you can consider three cases: w sigma*a, w sigma*ab, and w sigma* bb. Note, for example, that if w belongs to sigma*a, it also belongs to sigma*; therefore, as suggested by the statement, you need to show that there exists a computational path on w that terminates in q_1, and there also exists another computational path on w that terminates in q_2.

Solution

we have to prove 3 statement

1) q1 (q1,w) ;

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

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

Assume that w=xp, p is is either a or b, and |x|= n.

Thus, we assume it is true for x and task is to prove it for w,

since |w|= n+1.

1)q1 (q1, xp). This tells us that q1 (q1,x). p is either a or b

and transitions on both a and b go from q1 to q1 Thus statement 1 is proved

2)2. If p= a, the right hand side of statement 2 is true. Using statement 1

, we know that q1 (q1, x). Since there is a transition on a from q1to q2,

q2 (q1, xp), and the left hand side is also true

. If p= b, the right hand side of statement 2 is false.

Thus we have to show that q2 (q1,xp).

since the only transition into q2 is labeled with a.

3)suppose  w ends in ab. So if w=xp, p=b and x ends in a.

.applying statement 2 applied to x, q2 (q1, x).

(q2, b) = {q3}

hence 3 statement is also proved