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?

  • 2
    $\begingroup$ Absolutely not. The grammar may even become highly undecidable. $\endgroup$ – Emil Jeřábek Jun 8 '18 at 21:30
  • 1
    $\begingroup$ @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 >. $\endgroup$ – VermillionAzure Jun 8 '18 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.