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: 
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
4
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$.
-
$\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 '20 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 '20 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 '20 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 '20 at 14:37
$\begingroup$
$\endgroup$
2
I simplified your NFA and I got this DFA:
-
$\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 '20 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 '20 at 6:25
