GATE CS 2014 Set 1 Q36 — Regular Expressions and Finite Automata

The given DFA accepts the language of all binary strings ending with $1$. This language is directly represented by the regular expression III: $(0+1)^*1$.

Let us analyze the equivalence of the other expressions:

• Expression I: $0^*1(1+00^*1)^*$
  • Every string generated by this expression must end in $1$ because the initial part $0^*1$ ends in $1$, and any string chosen from the Kleene star $(1+00^*1)^*$ also ends in $1$.
  • It can generate any string ending in $1$. For example:
    • $1 \implies \epsilon \cdot 1 \cdot \epsilon$
    • $01 \implies 0 \cdot 1 \cdot \epsilon$
    • $101 \implies \epsilon \cdot 1 \cdot (01)$
  • Thus, Expression I is equivalent to $(0+1)^*1$.
• Expression II: $0^*1^*1 + 11^*0^*1$
  • Consider the string $w = 0101$, which ends in $1$ and must be accepted.
  • The first term $0^*1^*1$ cannot generate $0101$ because no $0$ can appear after a $1$.
  • The second term $11^*0^*1$ cannot generate $0101$ because it must start with $1$.
  • Since $0101$ is not represented, Expression II is incorrect.

Hence, only I and III represent the DFA.