GATE CSE 2008 | Question: 52

Question

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^*$

• A. $P-2, Q-1, R-3, S-4$
• B. $P-1, Q-3, R-2, S-4$
• C. $P-1, Q-2, R-3, S-4$
• D. $P-3, Q-2, R-1, S-4$

Comments

Do we need to solve this by taking a string from each RE and checking which NFAs accept it to eliminate options, or is there a more systematic approach that we should follow?

---

USE OPTION ELIMINATION TECHNIQE FOR THIS TYPE PROBLEM

---

Here after carefully observing, we can state that 

Notice only last one or two bits 

Opt. 1 :  01*    meaning endless 1 should be in final state............which is true only in P

Opt. 2 :  0       meaning ends with 0  ...........here we have two options either Q or S   BUT 

                                                               S have endless 0 loop in final state but our opt. does not have 0*

                                                               Hence, Q will match 
 

instead of Opt. 3 ,  check Opt. 4 first 

Opt. 4 : 10*   meaning ending with endless 0 .................exactly which we have seen in S
 

Now, as we know only one option is left then too for analysis let's go through that too,
 

Opt. 3 :  1    meaning end with only 1 not endless 1 .................which can be seen only in R
 

Hence, Answer is (C)

Answer 1

• For NFA P: starting at the initial final state gives $\epsilon$, and any non-empty path goes up via $0$, loops back and forth via $01^*1$ or $00$, and ends by reaching the right accepting state using $0$ and looping with $1^*$, giving $\epsilon + 0(01^*1 + 00)^*01^*$, which matches expression 1 ($P - 1$).

• For NFA Q: starting at the initial final state gives $\epsilon$, and moving up via $0$ allows looping through paths like $10^*1$ or $00$ before returning down to the start state via $0$, giving $\epsilon + 0(10^*1 + 00)^*0$, which matches expression 2 ($Q - 2$).

• For NFA R: starting at the initial final state gives $\epsilon$, and moving up via $0$ allows looping through paths like $10^*1$ or $10$ before returning down via $1$, giving $\epsilon + 0(10^*1 + 10)^*1$, which matches expression 3 ($R - 3$).

• For NFA S: starting at the initial final state gives $\epsilon$, and moving up via $0$ allows looping through paths like $10^*1$ or $10$ before ending at the right accepting state using $10^*$, giving $\epsilon + 0(10^*1 + 10)^*10^*$, which matches expression 4 ($S - 4$).

Combining all matches gives $P - 1, Q - 2, R - 3, S - 4$, which corresponds to option C.

Answer 2

To determine the correct matching, we analyze the paths and accepting states for each Non-deterministic Finite Automaton (NFA) :

 

• NFA P: The start state is an accepting state, which allows for the empty string $\epsilon$. From the top-left state, the automaton can loop back via the start state (a $00$ path) or via the top-right state (a $01^*1$ path). This forms a combined loop of $(01^*1 + 00)^*$. The automaton accepts by either returning to the start state (adding a final $0$) or stopping at the top-right state (adding a final $01^*$). This results in the regular expression $\epsilon + 0(01^*1 + 00)^*01^*$, matching expression 1.

• NFA Q: The start state is the only accepting state. The loop at the top-left state is formed by returning from the start state ($00$) or returning from the top-right state ($10^*1$). Because it only accepts at the start state, every accepted non-empty string must end with a $0$ transition back from the top-left state. The regular expression is $\epsilon + 0(10^*1 + 00)^*0$, matching expression 2.

• NFA R: The start state is the only accepting state, and the transition returning to it from the top-left is a $1$, making that loop component $10$. The loop through the non-accepting top-right state is $10^*1$. Accepting paths must end with the $1$ transition back to the start state. The regular expression is $\epsilon + 0(10^*1 + 10)^*1$, matching expression 3.

• NFA S: This NFA shares the exact same transitions as R, but the top-right state is also an accepting state. This introduces additional accepting paths that terminate in the top-right state, ending with $10^*$. Combining the paths for both accepting states gives the regular expression $\epsilon + 0(10^*1 + 10)^*10^*$, matching expression 4.

The analysis yields the matching $P - 1, Q - 2, R - 3, S - 4$. This corresponds exactly to Option C.

Answer 3

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