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

$S-4$ is confirmed

$R-3$ is true coz everything it accepts ends with $1$; this is made mandatory only by $3$
this rules out option B and option D 

use string $01010$ and compare $P$ Vs $Q$; this makes $Q-2$ as confirmed.

Hence, option C is correct.

Comments

Do most of the regular expression questions are solved by trial and error?

---

S not accepting 0101 hows its possible as all 4 option shows its S-4

---

In all the above regular expressions they are finding RE for middle state which is non final in all the NFA’s and then going to final state.

Answer 2

Lets go step by step by step, eliminating the given options:

Min string accepted by P is 00 , therefore 3, and 4 cant be the RE for it as they say 01 must be included.

Min string accepted by Q is 00 , therefore again 3, 4 cant be RE for Q for the same reason mentioned above.

So by now, we left only 2 options, answer has to be A or C.

2nd min accepted by P is 001, but RE in 2 says string start and end with 0. Therefore RE for P is 1 making 2 as RE for Q.

Therefore answer is Option C.

Comments

nice!

---

best and smart+ fast approch

Answer 3

Correct Ans is (C)

Trace the given regular expressions with the diagrams

Answer 4

for P 00 and 001* is accepted.so this can be generated with option 1 only

for S 01 and 010* can be generated.so this can be generated with option 4 only

Now we will compare rest of the options to distinguish them.

for Q 00 is accepted so option should be 2

for R 01 is accepted so option should be 3

(C) is the ans