Convert the regular expression to a NFA

2.7k Views Asked by At

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

1

There are 1 best solutions below

0
On

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