0
$\begingroup$

Having trouble figuring out a NFA for the following language, the objective is to use only 3 states:

$L = {\{1^ky : y \in \{0,1\}^* }\text{ and y contains atleast k 1's, for k} \ge 1 \}$

I have got to as far as the NFA below, which would only work if the y contains clause wasn't included:

enter image description here

So I need a different approach to this, but can't figure out how to go about it. Is there a different way of looking at the language that would make more sense for creating the NFA?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Your language is not regular, and no NFA will work. $\endgroup$ – orlp Sep 26 '20 at 22:50
  • $\begingroup$ Are you sure you're supposed to find an NFA and not a PDA (pushdown automaton)? $\endgroup$ – Ilkka Törmä Sep 27 '20 at 10:14
  • $\begingroup$ @orlp , that would certainly explain why I am having so much difficulty... many classmates seem to think it is possible, which further adds to the confusion. $\endgroup$ – SikhWarrior Sep 27 '20 at 17:02
  • $\begingroup$ @IlkkaTörmä yes, the question is design an NFA M such that L(M) = L. We have not covered PDAs yet, only DFA/NFA. $\endgroup$ – SikhWarrior Sep 27 '20 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.