patternMinor
Can a non-regular language be made regular via concatenation when they don't share characters?
Viewed 0 times
sharecanmadenonregularlanguageviawhencharactersconcatenation
Problem
So this is a follow-on question to my other question (Can we make a non-regular language regular via concatentation?).
Given the following,
$L = \{0^n1^m2^m \mid n>1, m>1\}$
$A = \{0^n \mid n>1\}$
$B = \{1^m2^m \mid m>1\}$
Is $L$ in fact just $A$ and $B$ concatenated (I believe it is, but I want to verify that)?
Further, does proving $B$ non-regular prove that $L$ is non-regular since they don't share characters?
Given the following,
$L = \{0^n1^m2^m \mid n>1, m>1\}$
$A = \{0^n \mid n>1\}$
$B = \{1^m2^m \mid m>1\}$
Is $L$ in fact just $A$ and $B$ concatenated (I believe it is, but I want to verify that)?
Further, does proving $B$ non-regular prove that $L$ is non-regular since they don't share characters?
Solution
First, the equality $L = AB$ is correct. Next, if you know that $B$ is non-regular, you can prove that $L$ is non-regular as follows.
Suppose that $L$ is regular. Then $(00)^{-1}L = \{0^n1^m2^m \mid n \geqslant 0, m>1\} = 0^B$ is regular. It follows that $0^B \cap \{1,2\}^* = B$ is regular. Contradiction.
Suppose that $L$ is regular. Then $(00)^{-1}L = \{0^n1^m2^m \mid n \geqslant 0, m>1\} = 0^B$ is regular. It follows that $0^B \cap \{1,2\}^* = B$ is regular. Contradiction.
Context
StackExchange Computer Science Q#55218, answer score: 3
Revisions (0)
No revisions yet.