Let Σ= {a, b}.
a. Consider the language S*, where S= {aa ab ba bb}. Give another description of this language.
b. Give an example of a set S such that S* only contains all possible strings of a’s and b’s that have length divisible by 3.

a.

S = {aa ab ba bb}

This clearly shows that that every string that belongs to this language has an even length including 0 length.

This language can be depicted as following

S* = {∧ aa ab ba bb aaab aaba aabb bbaa . . .}

Regular Expression for this can be

RE = (aa+ab+ba+bb)*

So S* contains all the strings of a's and b's that have even length. This means all strings of even length.

Explanation:

b.

S* contains all possible strings of a's and b's that have length divisible by 3

This means some of the possible strings examples are:

aaa, bbb, aaabbb, , and so on.

Length divisible by 3 means the length of string such as aaa is 3 which is divisible by 3, also   has length 6 which is divisible by 3

This should be something like this:

(( a + b ) ^3)*

For example a^3 = aaa which is divisible by 3

Regular expression can be:

RE of S* = (aaa + bbb)*

For example string has length 9 which is divisible by 3

So the language is

S* = { ∧ aaa bbb aaabbb bbb...}

go to the black logo in top left corner of page and click and you are there