Question

Automata, Computabity, Formal lang.

NOTE: Please show how you got the answer, thanks.

QUESTION: Give a regular expression for the following. The alphabet is {a, b}. All strings that start with 'a' and have odd length.

Answer 1

Accepted Strings:

These all strings are the part of the language so should be accepted by regular expression.

Example strings = {a, aaa, aba, aabba, aabbb,………}and all other strings that contain odd length strings and start with a.

Rejected Strings:

These all strings are not part of the language so should be rejected by regular expression.

Example strings = {b,aa, bb, ab, ba, aaaa, abba, abbb,……………..} and all other strings that start with b and do not contain odd length strings.

R.E = (a) (aa+bb+ab+ba)^*