3
$\begingroup$

Here is my proof:

Consider non-regular languages $$L_1 = \{a^i b^j | i \neq j\} $$ and $$L_2 = \{b^n a^m | n \neq m\}$$ Then the concatenation of these two languages would be $$L_1 L_2 = \{a^i b^{j+n} a^m | i \neq j \land n \neq m\}$$

when $i = 0, m = 0$: $j + n \geq 2$

when $i = 0, m \neq 0$ : $j + n \geq 1$

when $i \neq 0, m = 0$: $j + n \geq 1$

when $i = 1, j + n \neq 1$: $m = 1$

otherwise: $j+n \geq 0$

Thus, the concatenation of $L_1$ and $L_2$ could be expressed as the union of five regular languages $A_1$ to $A_5$, each corresponding to one of the conditions above (Each of these languages could be proven to be regular by drawing a simple finite state automaton):

$$A_1 = \{b^n | n \geq 2\}$$ $$A_2 = \{b^n a^m | n \geq 1 \land m > 0\}$$ $$A_3 = \{a^n b^m | n > 0 \land m \geq 1\}$$ $$A_4 = \{a b^n a | n \neq 1\}$$ $$A_5 = \{a^i b^j a^k | j \geq 0\}$$ $$L_1 L_2 = A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5$$ Since the union of regular languages are closed, $L_1 L_2$ is regular.

If such a proof is correct, then two more questions arise: Are there countably infinite amount of such examples (which the concatenation pf two non-regular languages is a regular language)? Are there uncountably infinite amount of such examples?

Here is my proof for the first question:

Suppose there are five sets of languages $S_1$ to $S_5$:

$$S_1 = \{L | L = \{b^n | n > p\}, p \geq 2\}$$ $$S_2 = \{L | L = \{b^n a^m | n \geq p \land m > q\}, p \geq 1 \land q \geq 0\}$$ $$S_3 = \{L | L = \{a^n b^m | n > p \land m \geq q\}, p \geq 0, \land q \geq 1\}$$ $$S_4 = \{L | L = \{a b^n a | n \geq p\}, p \geq 1\}$$ $$S_5 = \{L | L = \{a^i b^j a^k | j \geq p\}, p \geq 0\}$$

It is obvious that $S_1$ to $S_5$ are all countably infinite. A particular set $S$ of such possible example exists $$S = \{ L | L = L_1 \cup L_2 \cup L_3 \cup L_4 \cup L_5, L_1 \in S_1 \land L_2 \in S_2 \land L_3 \in S_3 \land L_4 \in S_4 \land L_5 \in S_5 \}$$

The cardinality of set $S$ is the cross product of set $S_1$ to $S_5$. A finite cross product of countably infinite sets is countably infinite. Thus, there are countably infinite amount of such examples.

Accordingly, since we could set $p$ and $q$ of set $S_1$ to $S_5$ to be numbers in the natural numbers set, an infinite amount of countably infinite sets similar to $S_1$ through $S_5$ exists. The (infinite) cross product of all these (countably infinite) sets is uncountably infinite. Thus, there are uncountably infinite amount of such examples.

Are my proofs right? Is there easier way to prove these questions?

$\endgroup$
  • $\begingroup$ For the initial example: In the second case you want $j+n\ge 1$, not $j+b\le 1$, and the fourth case should read ‘when $i=1,m=1:j+n\ne 1$’. $A_4$ should be $\{ab^na:n\ne 1\}$, and $A_5$ should be $\{a^ib^ja^k:i,k\ge 1,j\ge 0,\langle i,k\rangle\ne\langle 1,1\rangle\}$. Actually, you could combine $A_4$ and $A_5$ into $\{a^ib^ja^k:i,k\ge 1,j\ge 0,\langle i,j,k\rangle\ne\langle 1,1,1\rangle\}$. $\endgroup$ – Brian M. Scott Mar 18 '15 at 3:22
  • $\begingroup$ I have edited according to your corrections. What about the rest of the prove? Is it correct? $\endgroup$ – adlius45 Mar 18 '15 at 3:43
4
$\begingroup$

Take any nonregular language $L$. Denote by $L^c$ the complement of $L$ in $A^*$. Then the languages $1 + L$ and $1 + L^c$ are also nonregular. However, $A^* = L + L^c \subseteq (1 + L)(1 + L^c)$ and thus $(1 + L)(1 + L^c) = A^*$. This gives you uncountably many counterexamples, since there are only countably many regular languages and uncountably many subsets of $A^*$ if $A$ is nonempty.

Note: Here $+$ denotes union and $1$ denotes the language reduced to the empty word.

$\endgroup$
  • $\begingroup$ Excellent example! $\endgroup$ – Yuval Filmus Mar 19 '15 at 19:15
  • $\begingroup$ @yuval-filmus You are welcome. $\endgroup$ – J.-E. Pin Mar 20 '15 at 13:10
2
$\begingroup$

There are examples with $L_1 = L_2$. For example, take $L = \{ 1^p : p \text{ is an odd prime}\}$. If the Goldbach conjecture is true then $L^2 = (11)^+$ is regular, but $L$ isn't.

In order to get an unconditional example, consider the language $L = \{ 1^{a^2} : a \geq 0 \}$. It is easy to check that $L$ is not periodic – the distance between adjacent squares increases – and so $L$ is not regular. On the other hand, Lagrange's four square theorem shows that $L^4 = 1^*$. If $L^2$ is regular then $L^2$ is an example, and otherwise $L$ itself is an example. (In fact, $L^2$ is irregular, but this is a somewhat messy exercise.)

$\endgroup$
  • $\begingroup$ Could you please tell me how $(1^p)^*$ is equivalent to $1^*$ where p is prime number. As I can see "1" itself cant be generated. How is this true? $\endgroup$ – ViX28 Aug 9 '16 at 14:47
  • $\begingroup$ Fortunately, I'm never claiming that. $\endgroup$ – Yuval Filmus Aug 9 '16 at 14:50
  • $\begingroup$ Sorry!! I have read it at many places..just saw your concatenation example and that thought came. so asked its validity. $\endgroup$ – ViX28 Aug 9 '16 at 14:53
  • $\begingroup$ If the comment is not about my post, it shouldn't be a comment to my post. $\endgroup$ – Yuval Filmus Aug 9 '16 at 14:54
  • $\begingroup$ no i never meant that $\endgroup$ – ViX28 Aug 9 '16 at 14:58

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.