in Theory of Computation edited by
12,456 views
50 votes
50 votes

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 edited by
12.5k views

4 Comments

tnx :) @wander
0
0

Although not needed for solving, NFA S gives us the format by which we can derive other options. 

0
0

P -→ 1

1st Regular Exp can generate 000 
while NFA P can not generate 000

how is that valid ?

0
0

11 Answers

0 votes
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.

0 votes
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)
0 votes
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.
0 votes
0 votes
Q does not accept strings ending with 1. So, Q cannot correspond to 3 or 4.

R does not accept strings ending with 0. So, R cannot correspond to 1 or 2.

P accepts strings ending with 0 and also strings ending with 1. So, P cannot correspond
to 2 or 3.

Therefore answer is (c)
Answer:

Related questions