1
$\begingroup$

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

Could I get a hint on how to 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 $w_0=0$ and $w_1=0$

One solution that I found so far is that the regular expression $\alpha$ would be:

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

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

Could please someone clarify this one?

Thanks !

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.