Words are formed using the characters $0$ and $1.$ The length of a word is the number of characters in it. We say there is a path from word $x$ to word $y$ if starting from the word $x$ you can get the word $y$ by applying the following sequence of transformation rules finitely many times in any order.
- Replacing an occurrence of the string $101$ by a $0.$
- Replacing an occurrence of the string $010$ by a $1.$
- Replacing a $0$ by a $101.$
- Replacing a $1$ by by a $010.$
If there is a path from word $x$ to word $y$ we say $x$ and $y$ are equivalent or that they are in the same equivalence class. For example the four letter word $1011$ is equivalent to the two letter word $01,$ since the prefix $101$ in $1011$ can be replaced by a $0$ to get $01.$
We say $x$ has a shorter description if there is a word of shorter length equivalent to it.
- State true or false: for any word $x$ there is a unique shortest word in its equivalence class.
- How many three letter words are there in this language which have no shorter descriptions and which are all in different equivalance classes?
