in Theory of Computation edited by
6,276 views
36 votes
36 votes

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

in Theory of Computation edited by
6.3k views

4 Comments

@yuyutsu 
That’s correct. 

0
0

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

0
0

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

0
0

1 Answer

39 votes
39 votes
Best answer

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

edited by
by

4 Comments

@Praveen Saini can someone state about the part B
0
0

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

            

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

Related questions