Question

Let  Σ = { a, b }.

Which of the following strings cannot be represented by the RE

a* b* (ba)* a*?

Answer 1

A REGULAR EXPRESSION also called as RATIONAL EXPRESSION is a sequence of characters that define a search pattern.Search pattern can be anything :-

• a simple character,
• a fixed string or
• complex expression containing special characters describing the pattern

The strings(literals) that cannot be represented by the RE a* b* (ba)* a* :-

All the strings that can be generated till length-2 are definitely present in this language.

However, strings of length-3; {aaa, aab, aba, abb, baa, bab, bba, bbb} . String “bab” cannot be generated from given language. So, the string “bab” is the string not represented by given regular expression.