patternModerate
Can we make a non-regular language regular via concatentation?
Viewed 0 times
cannonmakeregularlanguageviaconcatentation
Problem
My question is basically given three languages A, B and L, where L is A and B concatenated together and B is proven to be non regular, is it possible to find an A that makes L regular?
Solution
Yes this is possible. Consider the example given below:
Let $B = 1^p$ where $p$ is prime. This is non regular.
Let $A = 1^n$ where $n \in \mathbb{N}$. This is regular.
$AB$ will simply give us $1^n$ with $n > 2$ and this is regular since any number greater than $2$ can be reprsent as $2+x$ where $x > 0$
Let $B = 1^p$ where $p$ is prime. This is non regular.
Let $A = 1^n$ where $n \in \mathbb{N}$. This is regular.
$AB$ will simply give us $1^n$ with $n > 2$ and this is regular since any number greater than $2$ can be reprsent as $2+x$ where $x > 0$
Context
StackExchange Computer Science Q#55141, answer score: 12
Revisions (0)
No revisions yet.