GATE CS 2008 Q52 — Regular Expressions and Finite Automata

We can easily match the NFAs to their corresponding regular expressions by analyzing the suffix of each expression (the part after the main loop) and comparing it with the transitions leading to and looping on the final state of each NFA.

Let's examine the suffixes of the four regular expressions:

• Expression 1: Ends with $01^*$. This corresponds to an NFA where the final state is entered via a $0$-transition and has a self-loop of $1$. This matches P.
• Expression 2: Ends with $0$. This corresponds to an NFA where the final state is entered via a $0$-transition and has no self-loop. This matches Q.
• Expression 3: Ends with $1$. This corresponds to an NFA where the final state is entered via a $1$-transition and has no self-loop. This matches R.
• Expression 4: Ends with $10^*$. This corresponds to an NFA where the final state is entered via a $1$-transition and has a self-loop of $0$. This matches S.

Thus, the correct matching is P-1, Q-2, R-3, S-4, which corresponds to Option C.