1.4k views

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

retagged | 1.4k views

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

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".
@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
Correct Ans is (C)

Trace the given regular expressions with the diagrams
–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.

OPTION IS C
edited ago