For each of the following regular expressions alpha find a s

For each of the following regular expressions alpha, find a shortest string we L(a): a^+ aabb^+ a^+ (bba)^+ b^+ a^+ aa(a + b)^+ For each of the languages sigma = {a, b}, find a regular expression representing it: All strings that contain exactly one a. All strings that contain at least two a\'s. All strings that begin with aa and end with bb. All strings that has a b followed by a.

Solution

1. shortest strings

a) a*aabb*

Solution: aab

b) a*(bba)*b*

Solution: bba

c) a*aa(a+b)*

Solution: aa

2.

(a) all strings containing exactly one a.

Solution (b + c)*a(b + c)*

(b) all strings containing at least two a\'s.

Solution: (a+b)(a+b)(a+b)*

(c) all strings that begin with two aa and end with bb.

Solution: aa(a+b)*bb

(d) all strings that has a b followed by a.

Solution: aba*