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?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ What do you think? $\endgroup$– Yuval FilmusCommented Sep 6, 2018 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. ♦Commented Sep 6, 2018 at 21:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Sep 6, 2018 at 15:35