8
$\begingroup$

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?

$\endgroup$
  • 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 '16 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 '16 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 '16 at 8:51
  • $\begingroup$ (This has probably been asked before, too.) $\endgroup$ – Raphael Mar 30 '16 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 Loveall Mar 31 '16 at 4:42
3
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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$

$\endgroup$
  • $\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$ – user48728 Mar 30 '16 at 22:05
12
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ To make it perhaps worse: let $B$ be any nonregular language and let $A = \varnothing$. Then $L = AB = A$ is regular. $\endgroup$ – Hendrik Jan Mar 30 '16 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$ – ymbirtt Mar 30 '16 at 16:52
  • $\begingroup$ @hendrik-jan You're perfectly right, and this is the best solution ! $\endgroup$ – J.-E. Pin Mar 30 '16 at 17:43
6
$\begingroup$

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.

$\endgroup$
  • $\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 '16 at 21:15
  • $\begingroup$ @Raphael Yes, that's a sufficient condition. $\endgroup$ – Gilles Mar 30 '16 at 21:20
0
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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