Please provide step by step solution thank you in advance 1. (20 points) Use ind

Question

Please provide step by step solution thank you in advance

1. (20 points) Use induction over the size of strings to prove that the fol- lowing NFA over the alphabet ta, b q1 92 93 a b recognizes the regular language Y ab (that is, it accepts all w EY that end with at Hint: use the following statement as induction hypothesis (1) For each string w E Y a (i.e., strings that end with an a) all existing computation paths terminate either in state q1 or in state q2 (note that we consider only those computation paths that do not "die" in the middle of the computation) (2) For each string w EY ab all existing computation paths terminate either in state g1 Or in state ga. (3) For every other string (which is neither in 2 a nor in 2 ab, i.e., it belongs to Y*bb U b UE), all existing computation paths terminate in state q1 Note that since state q3 is the only accept state, this statement implies that the language of the above NFA is y ab (see item (2)). Therefore by proving this statement we also prove that ab is the language of the above automaton. In the base case you need to show that the statement 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 fixed size n 2, assuming that it holds for all strings of size smaller than n For example, for each string w E a you need to show that there exists a computation path that terminates in q1 and there exists another comput tation path that terminates in q2. To do that you can consider the prefix of w of size n 1, for which the induction hypothesis holds

Explanation / Answer

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

hence this prove by induction

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.