Can we make a non-regular language regular via concatentation?

Question

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?

Answer 1

If we allow $A$ to be the empty language, which is regular, then we have that $L = \{w_1w_2 | w_1 \in A, w_2 \in B\} = \emptyset = A$.

For the slightly more interesting problem in which A must be a non-empty regular language, then we can construct a $B$ such that no non-empty $A$ results in a regular $L$

Let $B=\{bc^nd^n | n > 0\}$. Let $A$ be any regular language and consider $L=\{w_1w_2 | w_1 \in A, w_2 \in B\}$. Note that, contrary to the assumption in J.-E. Pin's answer, $B$ is irregular but doesn't contain the empty word.

Suppose $L$ is regular. There exists some DFA, $M=(S,\Sigma,\delta,q_0,F)$, which accepts $L$. Regardless of how $A$ is constructed, we know that every word in $L$ must have a last occurrence of $b$. Let $Q$ be the set of states travelled to immediately after the last $b$ in all possible accepting traversals. Note that $Q$ cannot be empty, since the shortest string in $B$ is $bcd$. Let $S'$ be the set of states visited in all possible accepting traversals at some point after the last $b$. Construct $M'=(S',\Sigma,\delta',q_0',F)$, where $\delta'$ behaves identically to $\delta$, except for the fact that $\delta'(q_0, \varepsilon)=Q$.

I claim that this NFA accepts the language $C=\{c^nd^n| n > 0\}$. For any $w' \in C$, we must have that there is some traversal from some element of $Q$ to some element of $F$, since $M$ must accept some string with this as a suffix. For any $w' \in \Sigma^{*} \setminus C$, we can pick a $w \in A$ and form the word $wbw'$. If $M'$ accepts $w'$, then it must be the case that $M$ accepts $wbw'$, since there must have been some traversal from some state in $Q$ to $F$ which is also valid for $M$. However, because of our choice of $w'$, it cannot be the case that $wbw' \in L$, so $M'$ must reject $w'$.

So $M'$ accepts $C$, but this language is not regular, leading to a contradiction.

Hence, if $A$ is non-empty, then $L$ cannot be regular.

Answer 2

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$

Answer 3

Let $\Sigma$ be a nonempty alphabet. Let $B$ be any nonregular language on $\Sigma$ containing the empty word and let $A = \Sigma^*$. Then $L = AB = A$ is regular.

Answer 4

Given a language $B$, the language $\varnothing B = \varnothing$ is regular. Apart from this trivial solution, it is not always possible to find a non-empty language $A$ such that $AB = \{uv \mid u \in A \wedge v \in B\}$ is regular. It is possible for many non-regular $B$ (e.g. if $B$ contains the empty word, or if $B$ is on a unary alphabet) but not for all $B$.

Take $B = \{ca^n \mid n\in\mathbb{P}\}$ where $\mathbb{P}$ is the set of primes. Whatever $A$ is, if $A$ is not empty then $AB$ is not regular, because to test membership in $AB$, it is necessary (due to the “stopper” symbol $c$) to use potentially unbounded memory to test the primality of the number of $a$'s at the end.

To prove this, let $u \in A$ (since we assumed that $A$ is not empty). If $AB$ is regular, then so is $L_1 = AB \cap uca^*$, and so is the left quotient of $L_1$ by the singleton $\{uc\}$ which is $L_2 = \{w \mid ucw \in AB \wedge ucw \in uca^*\} = \{w \in a^* \mid ucw \in AB\}$. This language is just $L_3 = \{a^n \mid n\in\mathbb{P}\}$ (if $w \in L_2$ then there exists $v\in A$ and $k\in\mathbb{N}$ such that $ucw = vca^k$, and since $w$ contains b^kno $c$, this implies that $w = a^k \in L_3$; conversely, if $w \in L_3$ then $cw \in B$ so $ucw \in AB$). $L_3$ is a well-known non-regular language, we have a contradiction.

Answer 5

While your question is asking for an existential proof, it reminds me of the branch of comp. sci. called Regular Approximations.

The idea is to take a non-regular language $L$ and then find a regular language $A$ such that $L \ominus A \rightarrow 0$ under some condition / subset of $L$ (where $\ominus$ is the symmetric difference), ie find a regular language which is "arbitrarily close" to $L$ for some subset that you care about. Often you accomplish this by taking a finite subset of $L$ with large measure over your subset of interest, and then concatenating it with a carefully chosen regular language.

You can find lots of interesting reads on Google Scholar if you search something like "regular language approximation context-free".