2
$\begingroup$

Given that $\#\notin \Sigma$ and $L\subseteq \Sigma^*\#\Sigma^*$, prove that if $L$ is context-free language then $L' = \{w_2\#w_1 \mid w_1\#w_2\in L\}$ is context-free. I'm trying to prove this in this way:

  1. because $L$ is context-free then $G$ is context-free grammar for $L$, then $L(G)=L$.
  2. by showing that the reversed grammar $F$ of $G$ is the same grammar of $L$ and because $G$ is context-free then $F$ is context-free then $L(F)=L'$ is also context-free. but can't figure out a way to prove this, so I need help to do this.
$\endgroup$
4
  • $\begingroup$ Note that $u\in L$ does not mean that the mirror word $\overline{u}\in L'$ (and conversely). $\endgroup$
    – Nathaniel
    May 15 at 11:38
  • $\begingroup$ then I can't prove the question by this way? $\endgroup$
    – Black Hat
    May 15 at 11:50
  • $\begingroup$ Indeed, I don't think so. $\endgroup$
    – Nathaniel
    May 15 at 12:04
  • $\begingroup$ any hint of another way that can work? $\endgroup$
    – Black Hat
    May 15 at 12:07

1 Answer 1

1
$\begingroup$

There is a unique path in the derivation tree that leads from the axiom $S$ to the terminal symbol $\#$. An idea would be to turn this tree upside down along that path.

This solution follows the construction for the closure under cyclic shift for context-free languages, as suggested in the book by Hopcroft and Ullman.

derivation trees

$\endgroup$
3
  • $\begingroup$ What do you mean by "to turn this tree upside-down along that path", is that to switch between the variables from the right side and left side? $\endgroup$
    – Black Hat
    May 15 at 14:01
  • $\begingroup$ I tried to explain that in the linked answer. $\endgroup$ May 15 at 14:05
  • 1
    $\begingroup$ Yeah, very nice and simple explanation thank you so much! $\endgroup$
    – Black Hat
    May 15 at 14:09

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.