TIFR CSE 2018 | Part B | Question: 2

Question

Consider the following non-deterministic automation, where $\large s_{1}$ is the start state and $\large s_{4}$ is the final (accepting) state. The alphabet is $\{a,b\}.$ A transition with label $\large\epsilon$ can be taken without consuming any symbol from the input.

Which of the following regular expressions corresponds to the language accepted by this automation ?

• A. $(a+b)^{*}aba$
• B. $aba(a+b)^{*}aba$
• C. $(a+b)aba(b+a)^{*}$
• D. $aba(a+b)^{*}$

• E. $(ab)^{*}aba$

Comments

correct option A...other (2,3) can be eliminated as minimum length string aba.....for 4th option consider string aaaaaaba.....and 5th is simple to eliminate....

---

A general question, can we not minimize option A,B,C,D to just (a+b)* . What am I missing here?

---

Without even checking strings, one can get the regular expression (a+b)*aba to reach the final state.

Answer 1

The correct option is (A).

Other option can be easily eliminated by using string bbaba.