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.

Question

contestada

Respuesta :

mahamnasir mahamnasir · Answer 1 · 2020-02-11T22:23:59+01:00

Answer:

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 aaaa 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, aaaaaa, bbbbbb and so on.

Length divisible by 3 means the length of string such as aaa is 3 which is divisible by 3, also aaaaaa 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 bbbbbbbbb has length 9 which is divisible by 3

So the language is

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