0
$\begingroup$

This question already has an answer here:

I am trying to prove this following theorem, can someone help please?

Let $L$ be a language over the alphabet $\Sigma = \{ a,b \}$. If $L' = \{ w\$w^R \mid w \in L\}$ is context-free, then $L$ is regular.

$\endgroup$

marked as duplicate by Gilles Jun 27 at 21:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ This is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – David Richerby Mar 28 '14 at 23:38
  • 2
    $\begingroup$ Intuitively, the stack of a PDA accepting $L'$ is needed to check $w$ against $w^R$, so only finite control remains to check $w \in L$. Can you expand that into a proof? $\endgroup$ – Raphael Mar 29 '14 at 11:34
  • 2
    $\begingroup$ I would say that this question is harder than average and so deserves more attention, though asking someone to solve it for you ruins both the fun and the learning experience; but this is the OP's decision. $\endgroup$ – Yuval Filmus Mar 29 '14 at 15:09
  • $\begingroup$ @YuvalFilmus: We have long since decided that hardness of the problem is not a factor in deciding whether to close such a question, but only its form. This is not Theoretical Computer Science, after all. I suggest you revisit the relevant meta posts. $\endgroup$ – Raphael Mar 29 '14 at 16:20
  • $\begingroup$ This is a duplicate of first half of context-free palindromes. The accepted answer to that question applies to this question verbatim except the replacement of "palindromes of even length" by "palindromes of odd length". $\endgroup$ – Apass.Jack Jun 27 at 15:37
3
$\begingroup$

Here is a proof sketch. The idea is to take a context-free grammar for $L'$ and come up with a regular grammar for $L$.

Start with a grammar for $L'$. Say that a language $M$ is symmetric if it is of the form $\{w \$ w^R : w \in P\}$ for some $P \subseteq \Sigma^*$. Prove that every non-terminal in $L'$ generates a language of one of the forms $w, wM, Mw$, where $w \in \Sigma^*$ and $M$ is symmetric. Consider two cases: the non-terminal generates a word without $\$$, or it generates a word with $\$$. In the first case, it's easy to see that it must generate a unique word. In the second case, every word it generates must contain $\$$, and the words need to be "compatible" in some sense, which implies that it generates a language of the form $wM$ or $Mw$.

For each non-terminal generating $wM$ or $Mw$, we can come up with a non-terminal generating the language $M$. This is because context-free languages are closed under this operation. So we can assume without loss of generality that each non-terminal either generates a unique word or a symmetric language.

Substitute all non-terminals generating unique words. All remaining productions must be of the form $A \to w B w^R$ or $A \to w \$ w^R$. We can come up with an equivalent grammar in which $w$ is always a symbol in the first case and empty in the second, so that all productions are now either $A \to a B a^R$ or $A \to \$$. If we replace these productions with $A \to a B$ and $A \to \epsilon$ then we get a right regular grammar for $L$.

For completeness, let me mention that the converse to the theorem also holds. You can see this by reversing the construction: from a right regular grammar for $L$, construct a context-free grammar for $L'$.

$\endgroup$
2
$\begingroup$

Since $L'$ is context-free, we consider a CF grammar $G=(V,T,P,S)$ for it, supposed to be reduced (all symbols are reachable and productive) and in Chomsky Normal Form (CNF).

We call spine any symbol that derives on a string containing $\$$, including $\$$ itself.

The start symbol $S$ is a spine. No right hand side of a rule contains more than one spine, since every string in $L$ contains exactly one $\$$.

Other than the spine, if any, no rule contains a symbol deriving on a recursive symbol. Because of CNF, a recursive symbol can generate terminal strings of any length. Suppose a rule $\pi$ contains a symbol deriving on a recursive one on the left of the spine, and a word $w\$w^R$ derived with that rule. Then the recursive symbol could be used to pump the length on the left side of the $\$$ without changing the other part, thus getting out of the language $L'$. Similarly for the right side.

Hence, all the non-spine symbols generate only finite sets of strings.

Then consider the grammar $H$ obtained from $G$ by removing all symbols right of the spine in all rules that have a spine, and also the $\$$ symbol itself. It clearly generate the language $L$ (by induction on derivation length). For every remainning non-spine non-terminal that derives on a set of $n$ terminal strings, replace each rule using it by $n$ rules, where it is successively replaced by each of the terminal strings. This does not change the language, and the grammar $H'$ for $L$, thus derived from $H$, is now right-linear. Hence $L$ is regular.

The converse is easily proved by building a PDA. It uses the finite control of a NFA for $L$ to check the first half of the string, while pushing it onto the stack. When it reads the $\$$, it just goes in popping mode and only check that each symbol read is equal to the stack top, which is then popped. If the stack is empty when the string is read, it is accepted.

Generalisation: Reading Yuval Filmus' answer (which I did after writing this one), I realized that it was even simpler to show that non-spine non-terminal generate a single terminal string, though it is a stronger property than generating a finite set of strings. I though at first I had made a mistake, but it is not the case, and the proof does hold. Actually, the proof would also hold with an even weaker property, that each non-spine non-terminal generates a regular set of terminal strings.

Then, it occurred to me that if weaker properties are enough to carry the proof, then it should be possible to extend the proof to more complex situations were only a weaker property can actually be proved. Here is an example, based on my current proof asserting finiteness of the set of terminal strings generated by a non-spine non-terminal:

Let $L'$ be a language included in $\{w\$w'\mid w\in L \wedge |w|=|w'|\}$and such that $\forall w\in L,\;\exists\ w\$w' \in L'$, then $L'$ is context-free implies that $L$ is regular

Note that this more general result implies trivially the result for the question asked by the OP.

$\endgroup$
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael Mar 29 '14 at 11:32
  • $\begingroup$ @Raphael Well received & reading meta. $\endgroup$ – babou Mar 29 '14 at 15:56
  • $\begingroup$ I do not want to edit this answer too often, but it seems that an even more general result from the above proof is given by considering that $L'\subseteq\{w\$w'\mid w\in L \wedge \exists g: \Sigma^*\rightarrow\mathbb N\; |w|<g(w') \}$ and $\forall w\in L,\;\exists\ w\$w' \in L'$. Then $L$ is regular if $L'$ is context-free. Note that the proof can ignore what happens on the right of the spine. All that matters is that there is a bound preventing arbitrary growth on the left. $\endgroup$ – babou Mar 29 '14 at 17:29

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