Write a regular expressions for the set of strings over the alphabet Σ = {a, b} containing at least one a and at least one b.

Question

Write a regular expressions for the set of strings over the alphabet Σ = {a, b} containing at least one a and at least one b.

Would the correct answer be R= a* + b*

Answer 1

Not quite. Your attempt there, instead, would only match a string of a's followed by a string of b's. It would not properly match, for instance, the string "ba". Think of it in this sense- if a string is composed of a's and b's, then necessarily if it contains both a's and b's then there must exist a substring of either "ba" or "ab". In that regard, we can figure that our regular expression must be as follows:

(a|b)*((ab)|(ba))(a|b)*

That is, we have a string of a's and b's, followed by an instance of "ab" or an instance of "ba", followed by a string of a's and b's. Because the middle operand is not optional in the context of the regular expression, there must exist either a substring "ba" or a substring "ab" in the string. Everything before and after that does not matter.

Answer 2

The smallest length of strings will be 2, "ab" or "ba".

First let us consider "a" will come first ("ab") : before "a", between "a" - "b" and after "b" it may consist any string or (a+b)*. So it will be (a+b) *a(a+b) *b(a+b) *.

For "ba" : before "b", between "b" - "a" and after "a" it may consist any string or (a+b)*. So it will be (a+b) *b(a+b) *a(a+b) *.

So the regular expression will be : (a+b) *a(a+b) *b(a+b) * + (a+b) *b(a+b) *a(a+b) *.