The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 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 (68.8k points)
retagged by | 1.4k views

3 Answers

+20 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 Veteran (30.5k points)
selected 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 Boss (6.3k points)
–1 vote
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 ago by (189 points)
edited ago by

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

32,443 questions
39,189 answers
36,563 users