The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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.5k points)
edited by | 1.9k views

4 Answers

+21 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.7k 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
+2 votes
Correct Ans is (C)

Trace the given regular expressions with the diagrams
answered by Loyal (6.1k points)
+2 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 (1.4k 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 (747 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

38,203 questions
45,703 answers
49,752 users