[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