edited by
12,503 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$
edited by

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

67 votes
67 votes
4 answers
1
Kathleen asked Sep 12, 2014
14,488 views
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state)$$\overset{Y}{\begin{array}{|l|l|l|}\hline \text{} & ...
34 votes
34 votes
2 answers
2