Which one of the following regular expressions correctly represents the language of the finite automaton given below?

Question

Match LIST-I with LIST-II \[\begin{array}{|c|c|c|}\hline \text{ } & \text{LIST-I} & \text{LIST-II} \\ \hline \text{A.} & \text{A Language L can be accepted by a Finite Automata, if and only if, the set of equivalence classes of $L$ is finite.} & \text{III. Myhill-Nerode Theorem} \\ \hline \text{B.} & \text{For every finite automaton M = $(Q, \Sigma, q_0, A, \delta)$, the language L(M) is regular.} & \text{II. Regular Expression Equivalence} \\ \hline \text{C.} & \text{Let, X and Y be two regular expressions over $\Sigma$. If X does not contain null, then the equation $R = Y + RX$ in R, has a unique solution (i.e. one and only one solution) given by $R = YX^*$.} & \text{I. Arden's Theorem} \\ \hline \text{D.} & \text{The regular expressions X and Y are equivalent if the corresponding finite automata are equivalent.} & \text{IV. Kleen's Theorem} \\ \hline \end{array}\]

\[\text{Matching List-I with List-II}\]

Choose the correct answer from the options given below:

Answer 1

To determine the correct regular expressions accepted by the given finite automaton, we analyze the structure of its states and transitions.

- The automaton allows repetitions of symbols using loops, which correspond to the Kleene star ($*$) or plus ($+$) operators in regular expressions.
- The transitions indicate alternating occurrences of the symbols a and b, with certain sequences allowed to repeat multiple times before reaching an accepting state.

Option (A):
This regular expression correctly captures the looping behavior of the automaton, allowing repeated and alternating patterns of a and b exactly as permitted by the transitions. Hence, it is accepted by the automaton.

Option (D):
This option also reflects the transition structure accurately, accounting for the valid paths and repetitions present in the automaton. Therefore, it is also a correct representation of the language accepted.

Other options:
The remaining options either allow strings that the automaton cannot generate or restrict valid repetitions that the automaton does allow, making them incorrect.

Final Answer: (A) and (D)

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

Show Hint

The Correct Option is D

Solution and Explanation

Top Questions on Regular expressions and finite automata

Questions Asked in GATE CS exam