I have the following deterministic finite automaton and I am need to prove corre

Question

I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts {wab?w?{a,b}?}

I know that I need to prove by induction on the length of the word but I am not sure how to do the induction step.

My try:

Anchor: After processing the only string of length zero, ?, the automaton is in state q0 as claimed.

Hypothesis: After reading a string u the automaton is in state q1 iff u=xa, and in state q2 iff u=xab and in q0 iff u=? or u=xb. The claim holds for input fragments of length up to n.

Step: Any string v of length n+1 is either v=ua or v=ub

We split to cases:

v=ua : According to the hypothesis- if u ends with b then it must be either in q0 or q2 - there for if we call a after that we get to q1 so ua is not accepted. Also, if u ends with a then it must be in q1 - there for if we call a after that we get to q1 so ua is not accepted.

v=ub : According to the hypothesis- if u ends with b then it must be either in q0 or q2 - there for if we call b after that we get to q0 so ub is not accepted. Also, if u ends with a then it must be in q1 - there for if we call b after that we get to q2 so ua is accepted.

I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts {wab?w?{a,b}?} I know that I need to prove by induction on the length of the word but I am not sure how to do the induction step. My try: Anchor: After processing the only string of length zero, ?, the automaton is in state q0 as claimed. Hypothesis: After reading a string u the automaton is in state q1 iff u=xa, and in state q2 iff u=xab and in q0 iff u=? or u=xb. The claim holds for input fragments of length up to n. Step: Any string v of length n+1 is either v=ua or v=ub We split to cases: v=ua : According to the hypothesis- if u ends with b then it must be either in q0 or q2 - there for if we call a after that we get to q1 so ua is not accepted. Also, if u ends with a then it must be in q1 - there for if we call a after that we get to q1 so ua is not accepted. v=ub : According to the hypothesis- if u ends with b then it must be either in q0 or q2 - there for if we call b after that we get to q0 so ub is not accepted. Also, if u ends with a then it must be in q1 - there for if we call b after that we get to q2 so ua is accepted.

Explanation / Answer

There is no induction needed. There is only one transition reaching the final state q2, namely q1?bq2. Furthermore, every transition reaching q1 is labelled by a. It follows that every word accepted by the automaton has to end by ab. It remains to prove that, conversely, any word of the form uab is accepted. After reading u from the initial state q0, you reach one of the three states q0, q1 or q2. It suffices now to observe that q0??abq2, q1??abq2 and q2??abq2. Thus q0???uabq2 in all cases, which means that uab is accepted.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---