Draw NFA.

Question

1) Design an NFA with no more than $5$ states for: $$L_1 = \left \{aba b^n \mid n \geq 0 \right \} \cup \left \{ ab a^n \mid n\geq 0 \right \}$$

2) Design an NFA with $3$ states for: $$L_2= \left \{a^n \mid n \geq 1 \right\} \cup \left \{ b^m a^k \mid m,k \geq 0\right \}$$

3) Design an NFA with $4$ states for: $$L_3= \left \{ a^n \mid n\geq 0 \right \} \cup \left \{b^n a \mid n \geq 1 \right \}$$

Answer 1

The NFA's for the given languages :

Comments

Please clarify about the ∈ transition on L1 , L2 and L3  ..Is it required...? even without that transition also the NFA will work correctly.right..?

---

Then try to generate aba* from L1 . Will you be able to generate without epsilon ? Moreover you may come up with different answer but my design needs epsilon . You can try without epsilon in less or equal number of steps .