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$
4
  • 2
    $\begingroup$ find the pattern a, ab, aba, abab, ababa, ababab, .abababa, ... $\endgroup$ Commented Jan 1, 2018 at 13:41
  • $\begingroup$ or $b, ba, bab, baba, \dots$. Kleene closure of something. $\endgroup$
    – fade2black
    Commented Jan 1, 2018 at 13:42
  • $\begingroup$ Would $((ab)^* \cup (ab)^* a) \cup ((ba)^* \cup(ba)^*b)$ work? $\endgroup$
    – user79878
    Commented Jan 1, 2018 at 13:44
  • 1
    $\begingroup$ @Leonhard It seems you gave your own answer! $\endgroup$ Commented Jan 1, 2018 at 14:08

3 Answers 3

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$
0
$\begingroup$

Empty or a singleton will work. Among the strings of at least two characters, $a$ and $b$ must alternate.

Hence $$b^+(ab)^*a^+$$

$\endgroup$
-2
$\begingroup$

(ab)(a+ε)+(ba)(b+ε) will work.

$\endgroup$

Your Answer

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