1
$\begingroup$

Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears even number of times is context-free?

$\endgroup$
  • 2
    $\begingroup$ What do you think? $\endgroup$ – Yuval Filmus Sep 6 '18 at 15:23
  • $\begingroup$ You've identified this as a quote. Any time that you copy or quote material from another source, please make sure to credit the original source. See cs.stackexchange.com/help/referencing. $\endgroup$ – D.W. Sep 6 '18 at 21:45
1
$\begingroup$

Add a new terminal $x$ to the alphabet, and replace $X$ with $xX$ in the right-hand side of all productions. Denote the corresponding context-free grammar by $G'$, and let $h\colon A \cup \{x\} \to A^*$ be the homomorphism erasing $x$. Then your language is $$ h(L(G') \cap A^*(xA^*xA^*)^*). $$ Since the context-free languages are xlosed under homomorphism and intersection with a regular language, it follows that your language is 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.