Question

Which of the following regular expression resembles the given diagram?

(a) {a}*{b}*{a,b}

(b) {a,b}*{aba}

(c) {a,b}*{bab}

(d) {a,b}*{a}*{b}*

The question was posed to me in a job interview.

This intriguing question originated from Introduction to Turing Machines topic in chapter Introduction to Turing Machines of Automata Theory

Answer 1

Right answer is (b) {a,b}*{aba}

The explanation: The given diagram is a transition graph for a turing machine which accepts the language with the regular expression {a,b}*{aba}.