0
$\begingroup$

I want to create a regular expression for the language

$L=\{ w \in \{a,b\} |$ w has neither aa nor bb as a subword$\}$.

I've tried various things, but I can't seem to get the correct regular expression.

$\endgroup$
  • 2
    $\begingroup$ find the pattern a, ab, aba, abab, ababa, ababab, .abababa, ... $\endgroup$ – Hendrik Jan Jan 1 '18 at 13:41
  • $\begingroup$ or $b, ba, bab, baba, \dots$. Kleene closure of something. $\endgroup$ – fade2black Jan 1 '18 at 13:42
  • $\begingroup$ Would $((ab)^* \cup (ab)^* a) \cup ((ba)^* \cup(ba)^*b)$ work? $\endgroup$ – user79878 Jan 1 '18 at 13:44
  • 1
    $\begingroup$ @Leonhard It seems you gave your own answer! $\endgroup$ – Hendrik Jan Jan 1 '18 at 14:08
0
$\begingroup$

$((ab)^∗∪(ab)^∗a)∪((ba)^∗∪(ba)^∗b)$ will work.

The possibilities are: $a,ab,aba,ababa,...$ or $b,ba,bab,baba,...$ or empty string

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy