1

Construct a Non-deterministic Finite State Automaton (NFA) M with minimum number of states for the set of strings over {0, 1} such that each 0 in the string is immediately followed by a 1.

The image below is the NFA i've drawn. However i do not know if it is correct. NFA

sleepgame eat
  • 11

1 Answers1

0

Your automaton is not correct. It accepts the word $0100$ which is not in the language.

Hint. There is a two-state deterministic automaton that recognizes your language.

J.-E. Pin
  • 40,163