6,276 views

Given below are the transition diagrams for two finite state machines $M_1$ and $M_2$ recognizing languages $L_1$ and $L_2$ respectively.

1. Display the transition diagram for a machine that recognizes $L_1.L_2$, obtained from transition diagrams for $M_1$ and $M_2$ by adding only $\varepsilon$ transitions and no new states.

2. Modify the transition diagram obtained in part (a) obtain a transition diagram for a machine that recognizes $(L_1.L_2)^*$ by adding only $\varepsilon$ transitions and no new states.

(Final states are enclosed in double circles).

That’s correct.

@yuyutsu one small mistake in b part is for state C there must be one self loop for alphabet a.

@yuyutsu
in part A in your solution state A wouldn’t be a final state.

We can combine the final state of $M_1$ with the start state of $M_2$ as follows recognizing $L_1L_2$. But before we combine $M_1$ and $M_2$ remove the final state of $M_1$ as the new machine can accept $L_1$ also while it should accept only $L_1.L2$.

~Pic by Praveeen Saini

by

@Praveen Saini can someone state about the part B

the regular expression for

L2 = { a^n.b.b^n  | n >=0 }

therefore, smallest possible string that L2 can generate is ‘”b “(not epsilon)

and, it is epsilon in case of L1.

As,  (epsion).(b) = b.

therefore ,, initial state cannot be an accepting state

M2 is a^n b^n ,n>=0;so epsilon can be accepted

1
4,323 views