in Theory of Computation edited by
7,985 views
41 votes

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^*$

  1. $P-2, Q-1, R-3, S-4$
  2. $P-1, Q-3, R-2, S-4$
  3. $P-1, Q-2, R-3, S-4$
  4. $P-3, Q-2, R-1, S-4$
in Theory of Computation edited by
8k views

7 Comments

S is not accepting 01011010. How is c possible?
2
Please someone provide reference for conversion of FA to R.E.
0
you can get the correct answer by looking at end of Final state incoming edges:

Incoming edges to FS for FA is

P.  01*

Q.  0

R. 1

S. 10*

Correct answer

P-1

Q-2

R-3

S-4

 

But if two FA having same incoming edges in that case you have check for remaining part of Regular Expression :)
16
DFA S will not generate string 01011010 as well as 4 also not generating the same string..

as both can generate 01011010 but not 01011010.
0
@prateek  S is accepting 0101  initial 0→ first  1→ initial 0→ first 1→ initial

And initial state is also final state
1
tnx :) @wander
0

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

0

Subscribe to GO Classes for GATE CSE 2022

10 Answers

34 votes
 
Best answer

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

edited by

8 Comments

moved by
1.   0010 should be accepted , only P is possible for it...

2. 0110 should be accepted , only Q is possible for it...

4 . 010 should be accepted.. Only possible by S.

So option C is Right..
4
the minimum value accepted by P is  0

but that isnt accepted by any of the options

where did i go wrong ?
0
The minimum value accepted by p is not 0. It's empty string.

Moreover p doesn't even accept "0".

Second minimal length string is "00".
0
@nymeria

in the diagram

only on input 0 it goes to accepting state right ?

to accept empty string the start state must be an accepting state , which is not so
0

@A_i_$_h In case of P, start state is the accepting state too.

0

Refer this link for conversion of the NFAs to regular expression

https://www.geeksforgeeks.org/gate-gate-cs-2008-question-52/

0
Do most of the regular expression questions are solved by trial and error?
0
S not accepting 0101 hows its possible as all 4 option shows its S-4
0
10 votes
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.

2 Comments

nice!
0
best and smart+ fast approch
0
2 votes
Correct Ans is (C)

Trace the given regular expressions with the diagrams
0 votes

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.

0 votes
Here is a slightly faster way of solving it and this type of problem in the exam:

1. Expressions 2. and 3. are easier to match with their NFA as they both have a fixed ending (2. has 'ends with 0' condition and 3. has 'ends with 1')

2. We can say that R-3 is one matching for sure just by observing the final state of R.

3. Looking at options that narrow it down to option A) or C). (We now also know S-4 is correct)

4. Now do the same for 2., it is definitely Q by observing final state.

Therefore it is option c)
0 votes
C is correct Answer Because you can checking just by the Language generating by the DFA and comparing them with the Given R.E...

For Example P={null,00,0010,00110, 001110,0011110.........}

         Q={null,00,01110,01010,010010,0100010......} similarily write the laguages genrating by the R & S. and match them with given Regular expressions.

by matching you will get ...

P1,Q2,R3,S4 as answer.
0 votes
Q does not accept strings ending with 1. So, Q cannot correspond to 3 or 4.

R does not accept strings ending with 0. So, R cannot correspond to 1 or 2.

P accepts strings ending with 0 and also strings ending with 1. So, P cannot correspond
to 2 or 3.

Therefore answer is (c)
0 votes
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.
0 votes

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

–2 votes
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
edited by
Answer:

Related questions