+26 votes
2.8k views

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$

edited | 2.8k views
0
S is not accepting 01011010. How is c possible?
0
Please someone provide reference for conversion of FA to R.E.
+4
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 :)

## 5 Answers

+23 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.

by Boss (30.5k points)
edited
+2
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..
0
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. +6 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. by Active (2.2k points) 0 nice! +2 votes Correct Ans is (C) Trace the given regular expressions with the diagrams by Loyal (5.8k points) 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.

by Junior (629 points)
–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
by Junior (785 points)
edited
Answer:

+35 votes
4 answers
1
+22 votes
1 answer
2
+34 votes
4 answers
3
+18 votes
1 answer
4