GATE CSE 1996 | Question: 12

Question

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

• A. 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.

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

Comments

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

---

It doesn't really make any difference tho

---

@JAINchiNMay, state A should be one of the final state in part A. Because $L_2$ contains epsilon. 

$L_1. \{\epsilon\} = L_1$

However, epsilon transition from state A to state C and State C as one of the final state cover that.

Answer 1

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

Comments

Language accepted by M1 is L1=(00+01+10+11)* and M2 is L2= a*b*.

So L1.L2=(00+01+10+11)* a*b*

In the both the DFA’s of Ques(a) and (b) state A can be final state as there is a null transition from A to C. So making A as final or non final doesn’t change the language accepted by FA.

---

yes that's definitely true here also we are accepting empty string ..

---

I think for part b  , null transition will be from D to A and C to A because in (L1.L2) , the last transition  will be either to state C (strings like 0011a) or state D (strings like 0011ab) but we have to again go to L1 to make our DFA accept strings that belongs to (L1.L2)$^*$ .

But adding null transition from A to D doesn't make sense because that things can be fulfilled by A to C null transition for strings like { $b,b^2$,.....}

Answer 2

Hi

Comments

No issues with the answer. That is perfectly fine.

Making DFA for those make the answer different from existing comments/answer.

---

it takes 15 days to understand , why there is epsilon from D to A .....

---

Caption