Consider the following problem:

$L$ is the language of regular expression $00^*11^*$. $DM(L)$ is the language obtained from $L$ by throwing away every even-length string belonging to it and for each odd-length string, removing the middle character. Determine what $DM(L)$ is, and tell whether or not it is regular.

Well, $L$ consists of all strings that have at least one $0$ followed by at least one $1$. After writing down a few strings in $L$ and then constructing $DM(L)$ from those, I came to the conclusion that $DM(L)$ consists of all even-length strings of $0$s and $1$s where all the $0$s precede all the $1$s. So, we either have an even number of $0$s followed by an even number of $1$s, or an odd number of $0$s followed by an odd number of $1$s. Note that the empty string $\epsilon$ is not in $DM(L)$. Therefore, a regular expression for $DM(L)$ is $$00(00)^*11(11)^* + 0(00)^*1(11)^*.$$ The first term of the regex takes care of even numbers of $0$s and $1$s and the second term takes care of odd numbers of both.

But, here's the official solution:

DM(L) is regular. L consists of all strings of at least one 0 followed by at least one 1. Any even-length string in 00*11* can be constructed by deleting the middle character from a string in L. A regular expression for DM(L) can be written $00(00)^*(11)^* + (00)^*11(11)^* + 0(00)^*1(11)^*$. Note that this expression guarantees not only that the string will be in 0*1*, but that its length is even --- i.e., either even numbers of 0's and of 1's (the first two terms) or odd numbers of both (the third term).

My issue with the official solution is that it permits the strings $00$ and $11$ to be in $DM(L)$, but that is not possible since all strings in $DM(L)$ must have at least one $0$ and at least one $1$. So, what is the correct regular expression for $DM(L)$?

  • 1
    $\begingroup$ The official solution is wrong - 00 is not in $DM(L)$ since neither of 000,010 are in $L$. I wouldn't trust any more official solutions from where you got this one. $\endgroup$ – Yuval Filmus Aug 28 '17 at 11:04
  • 1
    $\begingroup$ Why did this question get downvoted? Is this not the right place to ask such questions? If you know a better forum for this kind of question, please let me know. I spent quite some time in framing this question and I feel I've expressed my intent much better than most of the questions here. $\endgroup$ – SassySamurai Aug 28 '17 at 20:55
  • $\begingroup$ I agree. Some people here are rather trigger happy. $\endgroup$ – Yuval Filmus Aug 28 '17 at 21:29

Your Answer

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

Browse other questions tagged or ask your own question.