Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
5  
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. – D.W. Mar 30 at 5:16
1  
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. – D.W. Mar 30 at 5:16
    
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. – Raphael Mar 30 at 8:51
    
(This has probably been asked before, too.) – Raphael Mar 30 at 8:52
    
@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). – Kenny Loveall Mar 31 at 4:42
up vote 1 down vote accepted

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.

share|cite|improve this answer
    
You missed the trivial solution where $A$ is empty (and a sentence in your proof to explain why $M'$ accepts $\{c^nd^n\}$ — this fails if $Q = \varnothing$). – Gilles Mar 30 at 17:19
    
@Gilles If $A=\emptyset$ then $L$ can't exist. If $A=\{\varepsilon\}$ then $L=B$. Since $n>0$, the shortest string in $B$ is $bcd$, so there's always going to be a transition following the first $b$. I'll get working on adding some reasoning about why $M'$ accepts $\{c^nd^n\}$. – ymbirtt Mar 30 at 18:38
    
Ah, hold on, now I see your point. If $A$ is the empty language, $L$ is also the empty language. – ymbirtt Mar 30 at 18:40

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$

share|cite|improve this answer
    
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. – Tibor Mar 30 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.

share|cite|improve this answer
4  
To make it perhaps worse: let $B$ be any nonregular language and let $A = \varnothing$. Then $L = AB = A$ is regular. – Hendrik Jan Mar 30 at 16:04
    
This argument only works if $B$ contains the empty word. There exist irregular languages which do not contain the empty word. – ymbirtt Mar 30 at 16:52
    
@hendrik-jan You're perfectly right, and this is the best solution ! – J.-E. Pin Mar 30 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.

share|cite|improve this answer
    
Doesn't this proof work with any non-regular $B$ as long as the "stopper" symbol does appear only as such? – Raphael Mar 30 at 21:15
    
@Raphael Yes, that's a sufficient condition. – Gilles Mar 30 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".

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.