Ace Test Series: Theory Of Computation - Finite Automata

Question

Comments

M is NFA which accept a*b*a* and N also accept a*b*a*.

---

$L(M) \subset L(N)$, (A) should be the answer

---

yes L(M) is subset of L(N) . since M accept a*b*a* so N also.

Answer 1

Let us consider L(M) first :

So going by the automata from start state to final state , we get  :  a*b*a*

Now we consider L(N) :

Collapsing to single state , we get two incoming loops on q₀ ,

i.e. a and bb*  So we can write the regular expression as : (a + bb*)*

Now setting b* to ϵ , we get   :  (a + b)* 

Now obviously  L(M) is the subset of L(N).

Hence L(M)   ∩    L(N)   =   a*b*a*

Hence A) option should be correct .

Comments

Oh Yeah! Thanks @Anirudh @habibkhan

So, the best way here would be finding the RegExp of both FSM and then finding the relation between two.

---

Ya exactly

---

Setting here means we can substitute b* with epsilon but such substitution can be done inside Kleene's closure only , as it is ensured that no string will remain untouched by substituting b* to epsilon.

So if u have regular expression a + bb* you can not set b* to epsilon since this will result in a + b and hence bb, bbb , ..etc will not be covered which is wrong.

But since in the question a+bb* is within Kleene's closure so no problem