Skip to main content
empty language gives me an headache.
Source Link
Hendrik Jan
  • 31.1k
  • 1
  • 54
  • 107

Raphael is right: you can use a quite standard pumping argument. David Richerby is also right: your argument does not work in this way.

However ... If you want to have a result about closure of non-regular languages you can consider this one.

Theorem. If $L_1$ and $L_2$ are nonempty languages over disjoint alphabets, then their concatenation $L_1L_2$ is nonregular iff at least one of $L_1$ or $L_2$ is nonregular.

Of course, if either language is empty, then the concatenation will be empty, hence regular.

Raphael is right: you can use a quite standard pumping argument. David Richerby is also right: your argument does not work in this way.

However ... If you want to have a result about closure of non-regular languages you can consider this one.

Theorem. If $L_1$ and $L_2$ are languages over disjoint alphabets, then their concatenation $L_1L_2$ is nonregular iff at least one of $L_1$ or $L_2$ is nonregular.

Raphael is right: you can use a quite standard pumping argument. David Richerby is also right: your argument does not work in this way.

However ... If you want to have a result about closure of non-regular languages you can consider this one.

Theorem. If $L_1$ and $L_2$ are nonempty languages over disjoint alphabets, then their concatenation $L_1L_2$ is nonregular iff at least one of $L_1$ or $L_2$ is nonregular.

Of course, if either language is empty, then the concatenation will be empty, hence regular.

Source Link
Hendrik Jan
  • 31.1k
  • 1
  • 54
  • 107

Raphael is right: you can use a quite standard pumping argument. David Richerby is also right: your argument does not work in this way.

However ... If you want to have a result about closure of non-regular languages you can consider this one.

Theorem. If $L_1$ and $L_2$ are languages over disjoint alphabets, then their concatenation $L_1L_2$ is nonregular iff at least one of $L_1$ or $L_2$ is nonregular.