7,985 views

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

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$

S is not accepting 01011010. How is c possible?
Please someone provide reference for conversion of FA to R.E.
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*

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 :)
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.
@prateek  S is accepting 0101  initial 0→ first  1→ initial 0→ first 1→ initial

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

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

### Subscribe to GO Classes for GATE CSE 2022

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

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..
the minimum value accepted by P is  0

but that isnt accepted by any of the options

where did i go wrong ?
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".
@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

@A_i_$_h In case of P, start state is the accepting state too. Refer this link for conversion of the NFAs to regular expression https://www.geeksforgeeks.org/gate-gate-cs-2008-question-52/ 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 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! best and smart+ fast approch Correct Ans is (C) Trace the given regular expressions with the diagrams by 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.

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

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.

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.

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

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