# What is the interpretation of an infinite formal context-free grammar?

Let $L$ be a language as follows:

\begin{align*} L &::= a\ |\ L^{*}\\ \end{align*}

Now, suppose I apply some sort of transformation $T : N \rightarrow N$ where $N$ is the set of non-terminals in the grammar. Suppose that this results in $L$ being transformed into a modified version of $L$ by adding a unique prefix and postfix terminal to the $L^{*}$, and adding that new alternative parse to the grammar.

\begin{align*} L &::= & a\ |\ L^{*}\\ &\ | & (hello)\ L^{*}\ (bye) \end{align*}

As we apply $T$ infinitely many times to the context-free grammar, where the added terminals can be any arbitrary pairs of strings:

\begin{align*} L &::= & a\ |\ L^{*}\\ &\ | & (hello)\ L^{*}\ (bye)\\ &\ | & (hi)\ L^{*}\ (goodbye)\\ &\ | & (begin)\ L^{*}\ (end)\\ & \vdots & \vdots \end{align*}

...is the resulting grammar still context-free or is it now context-sensitive?

In short -- if a grammar has an infinite set of prefix/postfix pairs for a given non-terminal, is it a context-free grammar?

• Absolutely not. The grammar may even become highly undecidable. – Emil Jeřábek Jun 8 '18 at 21:30
• @EmilJeřábek Particularly the case I'm trying to model is that of XML without a schema. The matching tags component forces an infinite set of possible parse trees in the context-free grammar formalism as every single tag of the form < identifier > has a matching and unique tag "terminal" < / identifier >. – VermillionAzure Jun 8 '18 at 21:42