The Gateway to Computer Science Excellence
+33 votes
4k 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$
in Theory of Computation by
edited by | 4k views
0
S is not accepting 01011010. How is c possible?
0
Please someone provide reference for conversion of FA to R.E.
+10
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 :)
0
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.

7 Answers

+29 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
edited by
+4
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.

+7 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
0
nice!
+2 votes
Correct Ans is (C)

Trace the given regular expressions with the diagrams
by
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
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)
by
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.
by
–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
edited by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,469 answers
201,795 comments
95,272 users