Give some examples of strings in, and not in, these sets, where Σ = {a,b}

1.1k Views Asked by At

Here's the set:

{w : for some u ∈ Σ*, www = uu}

From what I understand, it's saying "w (which is a string) such that for some u (which is another string) is an element of the possible combinations of a and b, such that w concatenated three times is equal to u concatenated twice."

Would w = aaabb work as a solution? Because w would be a concatenated three times and u would be b concatenated twice. I would really appreciate it if someone could help me with this. Thank you!!

1

There are 1 best solutions below

0
On

$aaabb$ is an element of $\{w\in\Sigma^*: \exists u, v\in\Sigma^*(w=uuuvv)\}$. But this is not the same as $\{w\in \Sigma^*: \exists u(www=uu)\}$. The former is the set of $w$ such that $w$ can be written as a triple ("$uuu$") followed by a double ("$vv$") - in the case of $aaabb$, we take $u=a, v=b$ to see this. However, the latter - the set you're actually interested in - is the set of strings which, when tripled, equal some other string doubled.

Exercise: What is the relationship between the set you're interested in - $\{w: \exists u(www=uu)\}$ - and the set $\{w: \exists u(w=uu)\}$?