GATE CSE 2008 | Question: 52

Question

Match the following NFAs with the regular expressions they correspond to:

P

Q

R

S

 

1. $\epsilon + 0\left(01^*1+00\right)^*01^*$

2. $\epsilon + 0\left(10^*1+00\right)^*0$

3. $\epsilon + 0\left(10^*1+10\right)^*1$

4. $\epsilon + 0\left(10^*1+10\right)^*10^*$

• A. $P-2, Q-1, R-3, S-4$
• B. $P-1, Q-3, R-2, S-4$
• C. $P-1, Q-2, R-3, S-4$
• D. $P-3, Q-2, R-1, S-4$

Comments

tnx :) @wander

---

Although not needed for solving, NFA S gives us the format by which we can derive other options. 

---

P -→ 1

1^st Regular Exp can generate 000 
while NFA P can not generate 000

how is that valid ?

Answer 1

The NFA represented by P, accepts string “00” and then at final state (other than initial state) we have self loop of “1” , so we conclude that it must accept the string of the form of -> ϵ + 0 X* 01*, where X is regular expression (01*1 + 00 ) {resolving the loop at middle state}. It matches with statement 1.
Similarly, The NFA represented by Q, has the form of -> ϵ + 0X*0, where X is regular expression (10*1 + 00 ) {resolving the loop at middle state}. It matches with statement 2.
The NFA represented by R, has the form of -> ϵ + 0X*1, where X is regular expression (10*1 + 01 ) {resolving the loop at middle state}. It matches with statement 3.
The NFA represented by S, accepts string “01” and then at final state (other than initial state) we have self loop of “0” , so we conclude that it must accept the string of the form of -> ϵ + 0X* 10*, where X is regular expression (10*1 + 10 ) {resolving the loop at middle state}. It matches with statement 4.

Answer 2

Option C: P−1,Q−2,R−3,S−4

---

Explainations given in other answers are quite correct.

But to solve it quickly, check the condition to reach final state, like P ends with 1* since there’s a self loop on final state with input 1, similarly for S (0*). For Q and R, at the end there must be a 0 (for Q) or 1 (for R) to reach final state so regex will end with 0 (for Q) or 1 (for R).

Answer 3

for these kind of qst its better to go with trail and error (i.e by taking a valid string and by checking each FA but not to go with method) bcz this method takes lots of time which will kill around 5 mins

and i did like that (trail and error)
it takes
me only 2 mins.

OPTION IS C