[Solved]: Can we make a non-regular language regular via concatentation?

Problem Detail: 

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?

Asked By : Kenny Loveall

Answered By : ymbirtt

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55141