0
$\begingroup$

I'm new to regular expressions and I'm currently working on some exercises to get familiar in constructing regular expressions for languages. I have the following languages, for which I already tried to write the corresponding regular expressions.

Could you please tell me if they are correct or what I could improve? I would really appreciate your help.

$L_1 = \{w \in \{a, b\}^* : |w| \text{ is divisible by 3}\}$
$r_1=((a+b)(a+b)(a+b))^*$

$L_2 = \{w \in \{a, b\}^* : w \text{ contains } aa \text{ or } bb\}$
$r_2=(a+b)^*aa(a+b)^*+(a+b)^*bb(a+b)^*$

$L_3 = \{w \in \{a, b\}^* : w \text{ contains } aa \text{ and } bb\}$
$r_3=(a+b)^*aa(a+b)^*bb(a+b)^*$

$L_4 = \{w \in \{a, b\}^* : w \text{ contains } ab \text{ and } ba\}$
$r_4=(a+b)^*ab(a+b)^*ba(a+b)^*+(a+b)^*ba(a+b)^*ab(a+b)^*$

$L_5 = \{w \in \{a, b\}^* : |w|_a \le 1 \text{ or } |w|_b \ge 2\}$
$r_5=(b^*+b^*ab^*)+a^*bbb^*a^*$

$L_6 = \{w \in \{a, b\}^* : |w|_a \le 1 \text{ and } |w|_b \ge 1\}$
$r_6=(b*+b*ab^*)(a*bb^*a^*)$

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

$r_1$ and $r_2$ are correct, also I'd write $r_2$ shorter as $(a+b)^*(aa+bb)(a+b)^*$.

$r_3$ is wrong, note that $bbaa \in L_3$ isn't matched by $r_3$, $r_3$ matches the words which contain $aa$ before $bb$, you can fix this by writing $$ (a+b)^*\bigl(aa(a+b)^*bb + bb(a+b)^*aa\bigr) (a+b)^* $$ that is, just adding the other case.

$r_4$ is correct, here you got the point you were missing in $r_3$.

If $|w|_a$ denotes the number of $a$s (and the same for $b$'s), $r_5$ is wrong. The $a$-part is correct, but at least two $b$'s is $a^*ba^*b(a+b)^*$ (note that the $b$'s do not need to be connected), so we have $$ (b^* + b^*ab^*) + a^*ba^*b(a+b)^* $$

$r_6$ is also wrong, note that each of you $a^*$ can give as many $a$'s as we want, even more than one. $L_6$ consists of two types of words, those with no $a$ (given by the RE $bb^*$ [we need at least one $b$]) and those with one $a$, given by $b^*(ab+ba)b^*$ (note that we need one $b$), hence $$ r_6 = bb^* + b^*(ab+ba)b^* $$

$\endgroup$
1
  • $\begingroup$ Thank you so much! Your answer helped me a lot to understand my wrong reasoning. I got it now. $\endgroup$ Commented May 4, 2015 at 15:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.