1
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ It is really easy to come up with a DFA for your language. Then you can convert your DFA to a regular expression using standard techniques. $\endgroup$
    – Steven
    Commented Nov 4, 2021 at 15:38
  • $\begingroup$ cs.stackexchange.com/q/45570/755 $\endgroup$
    – D.W.
    Commented Nov 4, 2021 at 17:51

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.