The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 votes

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$
asked in Theory of Computation by Veteran (59.8k points)
edited by | 2.7k views
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*

Correct answer






But if two FA having same incoming edges in that case you have check for remaining part of Regular Expression :)

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

answered by Boss (30.9k points)
edited 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".

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.

+5 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.
answered by Active (2.1k points)
+2 votes
Correct Ans is (C)

Trace the given regular expressions with the diagrams
answered by Loyal (6.1k 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.

answered by Junior (741 points)
edited by

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
49,408 questions
53,589 answers
70,871 users