1
$\begingroup$

I'm new in theory of computation. Here {0,1} set of input symbols. I tried to make the NFA from L(M)= set of all accepted strings, but unable to complete it. Can someone give some hints that how should I attack this problem? . It will be very helpful.

$\endgroup$
1
$\begingroup$

This answer assumes that by substring you mean consecutive substring.

There is no need to use the power of NFAs. You can construct a DFA which remembers the following information:

  • The last symbol seen (either $0$, $1$, or blank).
  • The parity of number of occurrences of $01$ seen so far.

Maintaining the last symbol seen is easy. If the last symbol seen is $0$ and the current symbol is $1$, then you flip the parity of number of occurrences of $01$. A state is accepting if the parity of number of occurrences of $01$ seen so far is even.

I'll let you convert this description into an automaton.

$\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.