1
$\begingroup$

Let's say there is the alphabet {0,1} given and you are supposed to build a NFA for language L= {w | w includes two successive zeroes}.

So we are supposed to build a NFA for the language which only accepts words with two (or more) successive zeroes, where alphabet is {0,1}.

Now my question, is it allowed to build a NFA which only includes zeroes and no 1's?

$\endgroup$
  • $\begingroup$ What do you mean when you say an NFA "includes" zeroes, and not ones? Since the alphabet is $\{0, 1\}$ you do have to define behavior for when an $1$ is encountered in the input. For example $100$ is in the language, but contains an $1$. $\endgroup$ – orlp Oct 28 '17 at 15:27
  • 1
    $\begingroup$ It's allowed to build an NFA that only has transitions for input $0$s. But are you sure that's what you want? There are strings that contain two or more successive zeroes but also contain $1$s. $\endgroup$ – David Richerby Oct 28 '17 at 17:03

Your Answer

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

Browse other questions tagged or ask your own question.