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?
-
5$\begingroup$ Welcome to CS.SE! Our mission is partly to build up an archive of high-quality questions and their answers. Therefore, we'd prefer that you avoid changing the question in a way that invalidates existing answers, or that fundamentally changes what you are asking about; and we prefer you ask one question per question. Your initial question was a general one that is reasonable. Your EDIT asks some different questions. If you have a follow-up question, we'd prefer that you post it separately as a new question -- don't edit the original question. $\endgroup$– D.W. ♦Mar 30, 2016 at 5:16
-
1$\begingroup$ I'm going to remove the follow-on questions from this post, but you can find them with revision history if you want to post them separately. $\endgroup$– D.W. ♦Mar 30, 2016 at 5:16
-
$\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$– Raphael ♦Mar 30, 2016 at 8:51
-
$\begingroup$ (This has probably been asked before, too.) $\endgroup$– Raphael ♦Mar 30, 2016 at 8:52
-
$\begingroup$ @Raphael I did edit the question to contain the specific question I was wondering about and my logic, however it was removed by D.W. above. Also, this is not for my homework, it's because my professor didn't give me credit for a proof I did this way and I want to ensure my understanding is correct before going to talk with him about it (he's rather unreasonable to talk to, not to mention difficult to understand). $\endgroup$– Kenny LoveallMar 31, 2016 at 4:42
5 Answers
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.
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$
-
$\begingroup$ How about this? $B = 1^p$ and consider $BB$. It is trivial to see that $BB$ is isomorphic to $1^n$ where $n$ is an even number greater than 2, which is obviously regular. $\endgroup$– user48728Mar 30, 2016 at 22:05
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.
-
4$\begingroup$ To make it perhaps worse: let $B$ be any nonregular language and let $A = \varnothing$. Then $L = AB = A$ is regular. $\endgroup$ Mar 30, 2016 at 16:04
-
$\begingroup$ This argument only works if $B$ contains the empty word. There exist irregular languages which do not contain the empty word. $\endgroup$– ymbirttMar 30, 2016 at 16:52
-
$\begingroup$ @hendrik-jan You're perfectly right, and this is the best solution ! $\endgroup$ Mar 30, 2016 at 17:43
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.
-
$\begingroup$ Doesn't this proof work with any non-regular $B$ as long as the "stopper" symbol does appear only as such? $\endgroup$– Raphael ♦Mar 30, 2016 at 21:15
-
$\begingroup$ @Raphael Yes, that's a sufficient condition. $\endgroup$ Mar 30, 2016 at 21:20
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".