0

Let $S = \{a, b\}$ and let $X= \{w \mid \text{$w$ is a word over the alphabet $S$}\}$. For each language given below, list (if you can) two words which are in the language, and two words which are not in. (In either case, if there are no two such words, then explain why not.)

(a) $\{w ∈ X \mid \text{there are some $u, v ∈ X$ such that $uvw = wvu$}\}$

if $u = abb$, $v = baa$ and $w = ba$, $abbbaaba$ is not equal to $babaaabb$.

So how can every word over $S$ be in the language?

J.-E. Pin
  • 40,163
Jade
  • 21
  • Here's a MathJax tutorial :) – Shaun Jan 05 '22 at 16:50
  • 1
    For $w-ba$ you have to decide whether you can find words $u$ and $v$ that make the identity true, If so, then $ba$ is in the language. The fact that the identity fails for those two particular words $u$ and $v$ does not determine the fate of $w$. – Ethan Bolker Jan 05 '22 at 16:51
  • So then how are all words over S are in the language if it only works for some words u and v @Ethan Bolker – Jade Jan 05 '22 at 16:54
  • Why do you think every word is in the subset of $X$ described in (a)? The question asks you to find two words in that subset, and two words not, if that is possible. For $w=a$ you could take $u=v=a$ so $a$ is in the subset. (I assume you're not allowed to use the empty word for either $u$ or $v$.) – Ethan Bolker Jan 05 '22 at 17:04
  • 2
    Can‘t we just let $u = v := w$?! – martini Jan 05 '22 at 17:05
  • The set in (a) is$$A = {w \in X : \exists u\in X, \exists v\in X, uvw \ne wvu}$$ but you are treating it as if it were $$B = {w \in X : \forall u\in X, \forall v\in X, uvw \ne wvu}$$ Your example shows that $\text{ba} \notin B$, but it does not show $w \notin A$, since there are plenty of other words $u,v$ for which $uvw = wvu$. For example, as martini suggests $u = \text{ba}, v = \text{ba}$. – Paul Sinclair Jan 06 '22 at 18:28

0 Answers0