Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I need to find a regular expression for the language over $\{a,b,c\}$ consisting of all words in which no two consecutive letters are the same. For example, $abacbabca$ is in the language, while $abbc$ isn't.
How do I do that? Any help would be greatly appreciated!
Let's start with a regular expression for all non-empty words over $\{a,b\}$ without $aa$ or $bb$. Such words must alternate $a$'s and $b$'s, making it easy to construct a regular expression for this language.
Now let's consider the language of all words over $\{a,b,c\}$ without $aa,bb,cc$. Such a word is either empty, or of the form $w_1 c w_2 c \cdots w_{n-1} c w_n$, where $w_1,\ldots,w_n$ are words over $\{a,b\}$ without $aa$ or $bb$, and furthermore $w_2,\ldots,w_{n-1}$ are non-empty. Using this description, you can easily construct a regular expression for your language using the regular expression constructed in the preceding paragraph.
