I have tried to draw a deterministic finite automaton for the language L={any sequence of a and b, between two consecutive "b" there are maximum 3 "a"}:
Is it correct?
Asked
Active
Viewed 282 times
1
Mary Star
- 13,956
1 Answers
3
Not quite. Check inputs $bababababab$ and $baabaab$.
After your edit, $baabaab$ is still not accepted. We might suggestively name the four states $a^*$, $xb$, $xba$, $xbaa$, and $xbaaa$. Then reading $b$ should take you from any of the states to $xb$, whereas reading $a$ "moves right" by one state (except that it keeps you in $a^*$ and is "forbidden" for $xbaaa$)
Hagen von Eitzen
- 374,180
-
Do you mean that at the states 2,3,4 "b" should go to the first state? Or did I understand it wrong? – Mary Star Jan 18 '14 at 22:52