1
$\begingroup$

I'm trying to make non deterministic automata for specific language . I cant understand my mistake! Rules: 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

$\endgroup$
5
  • $\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 Dec 21 '20 at 18:34
  • $\begingroup$ @Jamāl yes!!!!! $\endgroup$ – user129239 Dec 21 '20 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$ – Dmitry Dec 21 '20 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$ – tylerhx111 Dec 22 '20 at 18:35
  • 4
    $\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 Dec 30 '20 at 17:07
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ thank you !!!!! $\endgroup$ – user129239 Dec 23 '20 at 7:41

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.