0
$\begingroup$

The Regular Expression i am having trouble with is the following a(b|bcc*)*c. My main concern is what do i do with the c*? I can lay the rest of the diagram correctly (i think) but that part is beyond me. Any help would be great, thank you. What i have: enter image description here

$\endgroup$
0
$\begingroup$

Your NFA does not recognize $abcc \in L$. To fix it you need to make $2$ non-final and then either:

  • Change the label of edge $(5,2)$ from $c$ to $\varepsilon$; or

  • Delete vertex $5$. Add the edges $(4,4)$ and $(4,2)$ with label $c$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I tried your first suggestion before and didnt work. Second one doesnt work either though it makes sense to me. Not sure where the problem is $\endgroup$ – megan Apr 27 at 13:00
  • $\begingroup$ Can you provide a word that is accepted (resp. is not accepted) by the modified NFA but is not in (resp. is in) the language? $\endgroup$ – Steven Apr 27 at 13:58
  • $\begingroup$ I see now that for some reason you made $2$ a final state. This is obviously wrong since the NFA accepts $a \not\in L$. To fix this you need to make $2$ non-final in addition to the modification I described in the answer, $\endgroup$ – Steven Apr 27 at 14:01
  • $\begingroup$ You are completely right, that was the problem. Its accepted now, thanks a ton for your help and time $\endgroup$ – megan Apr 27 at 14:37
0
$\begingroup$

I simplified your NFA and I got this DFA:

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting how this works (havent been that far yet into the course). Tried your last NFA but it gets an error: Incorrect definition of 'a(b|bcc*)*c'. Could be because the exercise asks to give an epsilon-NFA that recognizes the same language? $\endgroup$ – megan Apr 27 at 15:33
  • $\begingroup$ Sorry I did a mistake. [bc]* means that the input can also start with "c" and in your case it has to start with "b". $\endgroup$ – VimForLife Apr 28 at 6:25

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.