I'm trying to make a nondeterministic automaton for a specific language. I can't understand my mistake!


  1. {a,b,c}
  2. if I have the sequence "bb" and later in the word I have the sequence "cc" so this is not possible that I have the sequence "cba" between them.

Thank you!

enter image description here

  • $\begingroup$ so the language consists of all strings such that if they have $bb$ and $cc$ in that order, then there shouldn't be the string $cba$ in between them? $\endgroup$
    – Jamāl
    Commented Dec 21, 2020 at 18:34
  • $\begingroup$ @Jamāl yes!!!!! $\endgroup$
    – user129239
    Commented Dec 21, 2020 at 19:00
  • $\begingroup$ Why is it downvoted? I would do the following: 1) Build NFA for the complement language (it's pretty simple). 2) Build a corresponding DFA (there is a standard algorithm). 3) Convert to DFA for the original language (given a DFA, it's trivial to find a DFA for the complement language). $\endgroup$
    – user114966
    Commented Dec 21, 2020 at 19:46
  • $\begingroup$ The only problem I see is that $q4$ may need and transition to itself {a,b,c}. Without this, all strings in the language must end in cc. You should post the language this NFA is supposed to accept. $\endgroup$
    – tylerh111
    Commented Dec 22, 2020 at 18:35
  • 5
    $\begingroup$ Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 4.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work? $\endgroup$
    – Glorfindel
    Commented Dec 30, 2020 at 17:07

1 Answer 1


I have tried this question to the best of my ability. Feel free to ask for any clarification or raise any doubts in the comments.

enter image description here

Apart from issues like nullifying the effect of some useful transitions, the problem in your solution is that you've started out at a rejecting state, but unless the string has encountered $bb$ and then $cba$ and subsequently $cc$, it should be accepted.

I've laid out the transitions in a step wise manner, jumping about the states to "reset" the logic that proceeds to rejecting state.

Update: You can think about the automata as comprising of $3$ parts. q0,q1 check for first occurrence of $bb$. q2,q3,q4 detect the string $cba$. Finally, q5,q6,q7 test for the string $cc$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.