0
$\begingroup$

How can I make a finite automaton which does not end in string ab.

With the alphabet a,b

I made 3 states. For the first one it is accepting states and thus accept the empty string.

So here is a table I made. State 1 is initial state

        input   goes to state input goes to state

State 1 

         b       1             a      2

state 2

          b       3             a       2

state 3 

            b       3              a      3

But will it work?

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Draw a picture of it, test it on some words. Then, if you are happy with it, prove that it is correct. $\endgroup$ – Dave Clarke Feb 5 '15 at 20:34
  • $\begingroup$ You can use madebyevan.com/fsm to draw automata easily $\endgroup$ – User Feb 5 '15 at 21:02
4
$\begingroup$

Here is your suggested automaton, if I understand your transitions correctly (initial state is 1)

enter image description here

This automaton will only accept $\epsilon$, and words consisting of a number of $b$'s

Hints to make one that accepts your language:

Make sure that it accepts $\epsilon, a, b$ and make sure that you "move away" from accepting states when seeing a $b$ after an $a$ (keep in mind that $aabb$ is also a string in the language, i.e the second $b$ should make the machine go to an accepting state).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.