Constructing regular expressions for languages

70 Views Asked by At

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^*)$

1

There are 1 best solutions below

1
On BEST ANSWER

$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^* $$