1
$\begingroup$

I have to convert the following regular expressions to a NFA:

  1. $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$
  2. $$(((00)^{\star} (11)) \cup 01)^{\star}$$
  3. $$\emptyset^{\star}$$
  4. $$a(abb)^{\star} \cup b$$
  5. $$a^+ \cup (ab)^{\star}$$
  6. $$(a \cup b^+)a^+b^+$$

For the regular expressions $1-3$, $\Sigma=\{0,1\}$, and for the expressions $4-6$, $\Sigma=\{a, b\}$.

I have done the following:

enter image description here

Is this correct??

How is the NFA for the regular expression $3.$ ??

EDIT1:

enter image description here

EDIT2:

enter image description here

$\endgroup$
6
  • 1
    $\begingroup$ Since $\emptyset^* = \{\varepsilon\}$, the NFA for expression 3 is just one state which is both start and accept state with no outgoing transitions. $\endgroup$
    – mrp
    Mar 25, 2015 at 20:34
  • $\begingroup$ I see... Are the other NFA's correct?? @mrp $\endgroup$
    – Mary Star
    Mar 25, 2015 at 20:35
  • 1
    $\begingroup$ $(O \cup 1)^*$ is accepted by the one state automaton $\leftrightarrow 1 \xrightarrow{0,1} 1$. Therefore you can simplify a lot your solution for (1). $\endgroup$
    – J.-E. Pin
    Mar 25, 2015 at 20:50
  • $\begingroup$ I have added a new automaton for $(1)$. Could you take a look and tell me if this automaton is better?? @J.-E.Pin $\endgroup$
    – Mary Star
    Mar 25, 2015 at 20:58
  • 1
    $\begingroup$ @MaryStar Much better, but you could still merge the first two states and the last two ones. $\endgroup$
    – J.-E. Pin
    Mar 25, 2015 at 21:32

1 Answer 1

1
$\begingroup$

Your automata 1 is correct,

However the other are not:

2) You should be able to read several 00 before reading the 11 in the upper part since the regular expression is $(00)^*11$

4) a should be accepted by your automaton. You have to move the upper accepting state from the end of the sequence $abb$ to it's beginning (it's an $(abb)^*$ not $(abb)^+$

5) Again it's $(ab)^*$ hence the lower accepting state should be at the beginning of the sequence ab, and you should add a $\epsilon$ that allow to restart this sequence.

6) It's a $b^+$ you should be able to read several $b$'s hence add a loop reading $b$s on the lower state (between b and a).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .