Prove correctness of DFA ending with ab
-
02-11-2019 - |
Question
I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{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 $q_0$ as claimed.
Hypothesis: After reading a string u the automaton is in state $q_1$ iff $u=xa$, and in state $q_2$ iff $u=xab$ and in $q_0$ 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 $q_0$ or $q_2$ - there for if we call $a$ after that we get to $q_1$ so $ua$ is not accepted. Also, if $u$ ends with $a$ then it must be in $q_1$ - there for if we call $a$ after that we get to $q_1$ so $ua$ is not accepted.
- $v=ub$ : According to the hypothesis- if $u$ ends with $b$ then it must be either in $q_0$ or $q_2$ - there for if we call $b$ after that we get to $q_0$ so $ub$ is not accepted. Also, if $u$ ends with $a$ then it must be in $q_1$ - there for if we call $b$ after that we get to $q_2$ so $ua$ is accepted.
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange