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

Do we need to solve this by taking a string from each RE and checking which NFAs accept it to eliminate options, or is there a more systematic approach that we should follow?

---

USE OPTION ELIMINATION TECHNIQE FOR THIS TYPE PROBLEM

---

Here after carefully observing, we can state that 

Notice only last one or two bits 

Opt. 1 :  01*    meaning endless 1 should be in final state............which is true only in P

Opt. 2 :  0       meaning ends with 0  ...........here we have two options either Q or S   BUT 

                                                               S have endless 0 loop in final state but our opt. does not have 0*

                                                               Hence, Q will match 
 

instead of Opt. 3 ,  check Opt. 4 first 

Opt. 4 : 10*   meaning ending with endless 0 .................exactly which we have seen in S
 

Now, as we know only one option is left then too for analysis let's go through that too,
 

Opt. 3 :  1    meaning end with only 1 not endless 1 .................which can be seen only in R
 

Hence, Answer is (C)

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

 

mage widgetimage widget

Comments

For P, answer is => ε + 0(01*1 + 00)* 01*

---

Yes, made the correction , seems okay now.

---

writing is damn good

 

Answer 4

Correct Ans is (C)

Trace the given regular expressions with the diagrams

Answer 5

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

Answer 6

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 $\rightarrow$ ϵ + 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$\rightarrow$ ϵ + 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 $\rightarrow$ ϵ + 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 $\rightarrow$ ϵ + 0X* 10*, where X is regular expression (10*1 + 10 ) {resolving the loop at middle state}. It matches with statement 4.