1
$\begingroup$

I'm working on this problem :

Given the alphabet $\Sigma = \text{{0, 1}}$ find a regular expression to generate the language $L$, where : $L = \text{{w $\in$ $\Sigma^{*}$ | blocks of even length of 0's are separated by blocks of odd length of 1's }}$.

My problem is I seem to keep missing out a lot of strings, no matter what expression I come up with. There's something about this problem I can't wrap my head around.

Can you help with finding the expression?

$\endgroup$
  • $\begingroup$ Do you count $0$ as a possible length for the blocks? In particular, is $0011$ in your language? Here the block $11$ separates a block of $0$'s of length $2$ and a block of $0$'s of length $0$, but $11$ is of even length. $\endgroup$ – J.-E. Pin Oct 12 '16 at 18:16
2
$\begingroup$

HINT: I am going to assume that by block you mean a string of positive length. In that case $00(00)^*$ generates any block of zeroes, and $1(11)^*$ generates any block of ones.

Suppose that the langage were instead the set of words over $\Sigma$ in which zeroes and ones alternate. There are clearly four types of word in the language: those that begin and end with $0$, those that begin and end with $1$, those that begin with $0$ and end with $1$, and those that begin with $1$ and end with $0$. The regular expression $(01)^*$ generates all of the third type, and the regular expression $(10)^*$ generates all of the fourth type, so $(01)^*+(10)^*$ covers the words that begin and end with different characters. What about the first type? They can be got with $(01)^*0$, and the second type with $(10)^*1$. Thus, $(01)^*+(10)^*+(01)^*0+(10)^*1$ generates the desired language.

What you want is very similar, except that you want blocks to alternate rather than single zeroes and ones. You know how to get single zeroes and ones to alternate, and you know how to get the right kinds of blocks; all you have to do is combine the two properly.

$\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.