Regular expression for words that have the same number of 0s and 1s or contain 00 or 11

Question

I'm doing some Automata Theory exercises through a book and I'm trying to solve the exercise below but I can't figure out how to solve it.

Construct a regular expression that describe the following language given the alphabet $\Sigma = \{0, 1\}$, $$A = \{w \in \Sigma^ * : |w|_0 = |w|_1 \}\cup \Sigma^*\{00,11\}\Sigma^*.$$

Some examples that I think might be right:

00011 belongs to the language.
0does not belong to the language.
1does not belong to the language.
0011 belongs to the language.
01010101 belongs to the language.
$\lambda$ belongs to the language because $|\lambda|_0=0$ and $|\lambda|_1=0$.

One solution that I found so far is the regular expression:

$$\alpha = ((0 \cup 1) \Sigma^*)^*$$

However, to be honest, I am really not sure if this one is correct.

Could someone clarify this one?

Answer 1

Your $\alpha$ matches all strings, and is certainly incorrect.

The language is a union of two sets, so you can consider the two parts respectively and construct the regular expression with the form $R_1\mid R_2$.

The $\Sigma^*\{00,11\}\Sigma^*$ part is easy.

The $|w|_0=|w|_1$ part is somewhat tricky. You cannot construct a regular expression for $|w|_0=|w|_1$ because this language is not regular. However, You can only care about the set $S=\{w\mid |w|_0=|w|_1\text{but }w\notin\Sigma^*\{00,11\}\Sigma^*\}$ instead of the set $\{w\mid |w|_0=|w|_1\}$. Now try to figure out what $S$ looks like and write a regular expression for it. This is not hard.

Answer 2

The language of strings containing either 00 or 11 is clearly regular; it's easy to recognise.

The language of strings containing the same number of 0's and 1's is not even regular. But the whole problem is a trick question: The trick is that you don't need the strings containing the same number of 0's and 1's, but the same number of 0's and 1's but not containing 00 or 11.

What do the strings not containing 00 or 11 look like? Obviously there are the three strings eps, 0 and 1 which are too short. But otherwise, if your string starts with 0, the next character must be 1, then 0, then 1 and so on, and practically the same for strings starting with 1. In addition, the number of 0's and 1's must be the same if there is no 00 or 01.

So the strings are:

(01)*, (10)* # Same number of 0 and 1, no 00, no 11
(0|1)* (00 | 11) (0|1)* # Contains 00 or 11

and the regular expression is

(01)* | (10)* | (0|1)* (00 | 11) (0|1)*