HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can a non-regular language be made regular via concatenation when they don't share characters?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#55218, answer score: 3

Revisions (0)

No revisions yet.