Find three nonempty languages, $X, Y$ and $Z$ such that $XZ ⊆ YZ$, but $X$ is not a subset of $Y$.

Question

$X$, $Y$ and $Z$ are all regular languages that may span just over the alphabet $\{a\}$ or may span over larger alphabets: $\{a,b\}, \{a,b,c\}...$

The problem is that $X$, $Y$, and $Z$ make up from the same alphabet such that the concatenation of $X$ and $Z$ is a subset of $Y$ and $Z$, but the set $X$ is not a subset of $Y$.

The set $X$ is not a subset of $Y$ if all the elements of $X$ are included in the set $Y$. I don't really know how to approach this problem, any suggestions would be awesome Thank you.

Answer 1

I think if you let $X$ be the set of strings over $a$ with odd length, let $Y$ be the set of strings over $a$ of even length and let $Z $ be the set of strings over $a$ of any length, then I think that should work out.

Answer 2

HINT: Let $X=\{a^{2n+1}:n\in\Bbb N\}$ and $Y=\{a^{2n}:n\in\Bbb N\}$. Try to find a $Z$ that so that

$$XZ=\{a^n:n\ge 1\}\subseteq\{a^n:n\in\Bbb N\}=YZ\;.$$

(My $\Bbb N$ includes $0$.)

Answer 3

Hint. Let $A$ be the alphabet and let $X$ and $Y$ be languages containing the empty word. Then $XA^* = YA^* = A^*$.