<p>Let $L$ be a language as follows:</p>

<p>$$
\begin{align*}
L  &amp;::= a\ |\ L^{*}\\
\end{align*}
$$</p>

<p>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.</p>

<p>$$
\begin{align*}
L  &amp;::=  &amp;  a\ |\ L^{*}\\
   &amp;\ |  &amp; (hello)\  L^{*}\ (bye)
\end{align*}
$$</p>

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

<p>$$
\begin{align*}
L  &amp;::=  &amp;  a\ |\ L^{*}\\
   &amp;\ |  &amp; (hello)\  L^{*}\ (bye)\\
   &amp;\ |  &amp; (hi)\  L^{*}\ (goodbye)\\
   &amp;\ |  &amp; (begin)\  L^{*}\ (end)\\
   &amp;     \vdots &amp; \vdots
\end{align*}
$$</p>

<p>...is the resulting grammar still context-free or is it now context-sensitive?</p>

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

CC BY-SA 4.0
2018-06-08T21:30:14.140Z
Absolutely not. The grammar may even become highly undecidable.
Emil Jeřábek
CC BY-SA 4.0
2018-06-08T21:42:41.350Z
@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 >`.
CinchBlue
<fl.formal-languages><grammars><context-free>
What is the interpretation of an infinite formal context-free grammar?
CinchBlue
# What is the interpretation of an infinite formal context-free grammar?

(Asked by: username_0 on 2018-06-08)

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?

**Tags:** fl.formal-languages, grammars, context-free

> **Comments:**
> **username_1**: Absolutely not. The grammar may even become highly undecidable.  
> **username_0**: @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 >`.  

---

## 0 answers

