1
$\begingroup$

I came across following problem:

True or false? If $L$ is a regular and $M$ is not a regular language then $L.M$ is necessarily not regular.

The answer given was:

Consider $L$ to be $\emptyset$ and $M$ be $\{a^nb^n | n\leq 0\}$
$L.M=\emptyset$, which is regular. Hence the statement is false.

I guess the solution incorrectly tries to generalize the case of those two specific languages to all other languages. For example, if $M$ is DCFL, then I believe $L.M$ wont be regular. Am I correct with this?

$\endgroup$
  • 1
    $\begingroup$ The statement is "$L.M$ is necessarily not regular." A statement is false if there is a single counter-example, which that solution provides. No "generalisation" is involved. (Also, $M$ is a DCFL, so your conjecture is wrong.) $\endgroup$ – rici Dec 25 '19 at 18:30
  • $\begingroup$ ohhh so, "is necessarily not regular" means "is not regular", whereas "not necessarily regular" means "may or may not be regular" (never came across word usage "necessarily not", it was always "not necessarily") $\endgroup$ – anir Dec 25 '19 at 18:35
  • 2
    $\begingroup$ Yep. It means "is always (not regular)". $\endgroup$ – rici Dec 25 '19 at 18:39
  • 1
    $\begingroup$ A more interesting version of this question is: for which languages $L$ is it the case that for all languages $M$, the language $LM$ is regular. $\endgroup$ – Yuval Filmus Dec 25 '19 at 23:50
  • 1
    $\begingroup$ I meant exactly what I wrote. $\endgroup$ – Yuval Filmus Dec 26 '19 at 7:45
2
$\begingroup$

As you show, if $L = \emptyset$ then $LM$ is regular for any language $M$. Conversely, for languages over $\{0,1\}$ (or any non-unary alphabet), there is a language $M$ such that if $L \neq \emptyset$ then $LM$ is not regular: $$ M = \{10^p : p \text{ prime}\}. $$ Indeed, suppose that $w \in L$. Then $$ w^{-1}(LM \cap w10^*) = M. $$ Since all of the operations preserve regularity, we conclude that $LM$ is not regular.

Over a unary alphabet, the picture is a bit different. Let $$ M = \{ 0^{n!} : n \geq 0 \}. $$ If $L \neq \emptyset$ is finite then $LM$ is not eventually periodic, and so not regular. If $L$ is infinite and not regular, then $L\{\epsilon\}$ is not regular. If $L$ is infinite and regular, then it is eventually periodic. For every language $M$, $LM$ is also eventually periodic (with the same period), and so regular.

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