Construct a Non-deterministic Finite State Automaton (NFA)

47 Views Asked by At

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

1

There are 1 best solutions below

1
On

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.