<p>There was a closely related question (and several answers) on MathOverflow about the languages whose <a href="https://mathoverflow.net/questions/8262/is-there-a-natural-family-of-languages-whose-generating-functions-are-holonomic">generating functions are holonomic</a>.  </p>

<p>Interestingly, Neel's definition of the semantics of $\mu$ above corresponds <em>exactly</em> to the (constructive) proof of the existence of Species solutions to recursive Species equations via the implicit Species theorem.  Unfortunately, his proof outline must also contain a subtle mistake, as there are cases where things go 'infinite'.  In other words, there is a condition on the Jacobian of the transformation defined by the grammar to be non-singular which is needed.  This is probably why Bonsangue-Rutten require the fixed points to be guarded, as one way to insure this condition on the Jacobian.</p>

CC BY-SA 3.0
2013-03-31T19:33:43.273Z
AFAICT, Winter et al only require guardedness in order to ensure you can take the Brzozowski derivative of $\mu\alpha.\;g$ by taking the derivative of $[\mu\alpha.\;g/\alpha]g$.
Neel Krishnaswami
CC BY-SA 3.0
2013-03-30T13:05:05.567Z
2013-03-30T13:05:05.567Z
2017-04-13T12:57:54.777Z
Jacques Carette
<p>Yes.</p>
<p>A simple example should suffice to show both what and how.</p>
<p>Consider the grammar given by
<span class="math-container">$$S → x,\quad S → u S v.$$</span>
This specifies a subset of <span class="math-container">$\{u,x,v\}^*$</span> and - more generally - a context-free subset of a monoid <span class="math-container">$M ⊇ \{u,x,v\}$</span> that may, but need not, be free. (<a href="https://softwareengineering.stackexchange.com/questions/253454/what-does-context-free-mean-in-the-term-context-free-grammar/452893#452893">Context-Free Grammars Over Arbitrary Monoids</a>).</p>
<p>Extend <span class="math-container">$M$</span> with the inclusion of <span class="math-container">$Z = \{b,d,p,q\}$</span>, subject to the identities <span class="math-container">$bd = 1 = pq$</span>, <span class="math-container">$bq = 0 = pd$</span> and <span class="math-container">$mz = zm$</span>, for <span class="math-container">$m ∈ M$</span> and <span class="math-container">$z ∈ Z$</span>. Then we may write
<span class="math-container">$$S = b (u p)^* x (q v)^* d.$$</span></p>
<p>This is the contemporary form of an expression that would, in earlier times, have been arrived at by way of the <a href="https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_enumeration_theorem" rel="nofollow noreferrer">Chomsky-Schützenberger [Enumeration] Theorem</a>, and the framework underlying it is an evolutionary descendant of this result</p>
<p><a href="https://math.stackexchange.com/questions/4843156/how-to-show-that-only-this-regular-expression-solves-this-equation/4890511#4890511">The Algebraic Underpinning To Context-Free Expressions</a></p>
<p><a href="https://cs.stackexchange.com/questions/42269/rational-subsets-of-a-monoid/167534#167534">The Algebras And Categories Associated With Rational And Context-Free Subsets Of Monoids</a></p>
<p><a href="https://www.cambridge.org/core/services/aop-cambridge-core/content/view/B423ED951CD154761D1CCAE96A99BC4F/S0960129522000329a.pdf/an-algebraic-representation-of-the-fixed-point-closure-of-continuous-kleene-algebras-a-categorical-chomsky-schutzenberger-theorem.pdf" rel="nofollow noreferrer">An algebraic representation of the fixed-point closure of ∗-continuous Kleene algebras – A categorical Chomsky–Schützenberger theorem</a></p>
<p>Another example, that better illustrates the true nature and extent of this new framework, involves the following translation grammar
<span class="math-container">$$
E → u E v,\quad E → w E α,\quad E → E y E β,\quad E → x γ,\quad S → E z ω,
$$</span>
which specifies a subset of <span class="math-container">$X^* × Y^*$</span>, where <span class="math-container">$X = \{u,v,w,x,y,z\}$</span> and <span class="math-container">$Y = \{α,β,γ,ω\}$</span>, or - more generally - a context-free subset of a monoid <span class="math-container">$M × N$</span>, where <span class="math-container">$M ⊇ X$</span>, <span class="math-container">$N ⊇ Y$</span> - may be given by a context-free expression corresponding to the following &quot;linearization&quot; of the above grammar:
<span class="math-container">$$
E_0 → u ⟨1| E_0,\quad E_0 → w ⟨2| E_0,\quad E_0 → x γ E_1,\\
E_1 → y ⟨3| E_0,\quad E_1 → E_2,\\
E_2 → |0⟩ z ω,\quad E_2 → |1⟩ v E_1,\quad E_2 → |2⟩ α E_1,\quad E_2 → |3⟩ β E_1,\\
⟨0| E_0
$$</span>
with the last item being the top-level expression. Here, we may set
<span class="math-container">$$
⟨0| = bb,\quad ⟨1| = bp,\quad ⟨2| = pb,\quad ⟨3| = pp,\\
|0⟩ = dd,\quad |1⟩ = qd,\quad |2⟩ = dq,\quad |3⟩ = qq
$$</span>
to capture the conditions <span class="math-container">$⟨i| |i⟩ = 1$</span> and <span class="math-container">$⟨i| |j⟩ = 0$</span> if <span class="math-container">$i ≠ j$</span>; and we have, here, the identities:
<span class="math-container">$$x y = y x,\quad y z = z y,\quad z x = x z,\quad(x ∈ X,\quad y ∈ Y,\quad z ∈ Z),$$</span>
along with <span class="math-container">$bd = 1 = pq$</span> and <span class="math-container">$bq = 0 = pd$</span>. The corresponding context-free expression is
<span class="math-container">$$
⟨0| F (y ⟨3| F)^* |0⟩ z ω,
$$</span>
where
<span class="math-container">$$
F = (u ⟨1| + w ⟨2|)^* x γ (|1⟩ v + |2⟩ α + |3⟩ β)^*.
$$</span></p>
<p>If the grammar is thought of as a translation from prefix/infix order (with operators <span class="math-container">$w,y$</span> and brackets <span class="math-container">$u,v$</span>) to postfix order (with operators <span class="math-container">$α,β$</span>), then this is a context-free <em>translation</em> expression. When written as a linearized grammar, it may equally-well be interpreted as a parser that produces output &quot;actions&quot; <span class="math-container">$α,β,γ,ω$</span> and reads input &quot;symbols&quot; <span class="math-container">$u,v,w,x,y,z$</span>.</p>
<p>It can be equally-well be written in a form that collates all of the <span class="math-container">$Y$</span> and <span class="math-container">$Z$</span> &quot;actions&quot; by merging <span class="math-container">$E_1$</span> and <span class="math-container">$E_2$</span> and factoring out <span class="math-container">$|2⟩ α + |3⟩ β$</span>, rewriting the linearized grammar (with the aid of the commutativity relations on <span class="math-container">$X$</span>, <span class="math-container">$Y$</span> and <span class="math-container">$Z$</span>) as:
<span class="math-container">$$
E_0 → u ⟨1| E_0,\quad E_0 → w ⟨2| E_0,\quad E_0 → x γ E_1,\\
E_1 → y G ⟨3| E_0,\\
E_1 → z G |0⟩ ω,\quad E_1 → v G |1⟩ E_1,\\
⟨0| E_0
$$</span>
and with the corresponding context-free expression:
<span class="math-container">$$⟨0| F (y G ⟨3| F)^* z G ω |0⟩$$</span>
where
<span class="math-container">$$F = (u ⟨1| + w ⟨2|)^* x γ (v G |1⟩)^*,\quad G = (|2⟩ α + |3⟩ β)^*.$$</span></p>
<p>The pulling of the elements of <span class="math-container">$X$</span> out to the front, with commutativity, may be regarded as the algebraic form of a &quot;look-ahead&quot;.</p>

CC BY-SA 4.0
2024-04-18T17:22:41.730Z
2024-04-18T17:43:18.757Z
2024-04-18T17:43:18.757Z
NinjaDarth
<p>Yes, there is. Define a <em>context-free expression</em> to be a term generated
by the following grammar:</p>
<p><span class="math-container">$$
\begin{array}{lcll}
g &amp; ::= &amp; \epsilon &amp; \mbox{Empty string}\\ 
  &amp;  |  &amp; c        &amp; \mbox{Character $c$ in alphabet $\Sigma$} \\ 
  &amp;  |  &amp; g \cdot g &amp; \mbox{Concatenation} \\ 
  &amp;  |  &amp; \bot      &amp; \mbox{Failing pattern} \\  
  &amp;  |  &amp; g \vee g  &amp; \mbox{Disjunction}\\
  &amp;  |  &amp; \mu \alpha.\; g &amp; \mbox{Recursive grammar expression} \\
  &amp;  |  &amp; \alpha    &amp; \mbox{Variable expression}
\end{array}
$$</span></p>
<p>This is all of the constructors for regular languages except Kleene
star, which is replaced by a general fixed-point operator <span class="math-container">$\mu
\alpha.\;g$</span>, and a variable reference mechanism. (The Kleene star is
not needed, since it can be defined as <span class="math-container">$g\ast \triangleq \mu
\alpha.\;\epsilon \vee g\cdot\alpha$</span>.)</p>
<p>The interpretation of a context-free expression requires accounting
for the interpretation of free variables. So define an <em>environment</em>
<span class="math-container">$\rho$</span> to be a map from variables to languages (i.e., subsets of
<span class="math-container">$\Sigma^*$</span>), and let <span class="math-container">$[\rho|\alpha:L]$</span> be the function that behaves
like <span class="math-container">$\rho$</span> on all inputs except <span class="math-container">$\alpha$</span>, and which returns the
language <span class="math-container">$L$</span> for <span class="math-container">$\alpha$</span>.</p>
<p>Now, define the interpretation of a context-free expression as follows:</p>
<p><span class="math-container">$$
\newcommand{\interp}[2]{[\![{#1}]\!]\;{#2}}
\newcommand{\setof}[1]{\left\{#1\right\}}
\newcommand{\comprehend}[2]{\setof{{#1}\;\mid|\;{#2}}}
\begin{array}{lcl}
\interp{\epsilon}{\rho} &amp; = &amp; \setof{\epsilon} \\ 
\interp{c}{\rho}        &amp; = &amp; \setof{c} \\ 
\interp{g_1\cdot g_2}{\rho} &amp; = &amp; \comprehend{w_1 \cdot w_2}{w_1 \in \interp{g_1}{\rho} \land w_2 \in \interp{g_2}{\rho}} \\ 
\interp{\bot}{\rho} &amp; = &amp; \emptyset \\ 
\interp{g_1 \vee g_2}{\rho} &amp; = &amp; \interp{g_1}{\rho} \cup \interp{g_2}{\rho} \\ 
\interp{\alpha}{\rho} &amp; = &amp; \rho(\alpha) \\ 
\interp{\mu \alpha.\; g}{\rho} &amp; = &amp; \bigcup_{n \in \mathbb{N}} L_n \\ 
\mbox{where} &amp; &amp; \\ 
L_0 &amp; = &amp; \emptyset \\ 
L_{n+1} &amp; = &amp; L_n \cup \interp{g}{[\rho|\alpha:L_n]}
\end{array}
$$</span></p>
<p>Using the Knaster-Tarski theorem, it's easy to see that the
interpretation of <span class="math-container">$\mu \alpha.g$</span> is the least fixed of the expression.</p>
<p>It's straightforward (albeit not entirely trivial) to show that you
can give a context-free expression deriving the same language as any
context-free grammar, and vice-versa. The non-triviality arises from
the fact that context-free expressions have nested fixed points, and
context-free grammars give you a single fixed point over a tuple. This
requires the use of Bekic's lemma, which says precisely that a nested
fixed points can be converted to a single fixed point over a product (and
vice-versa). But that's the only subtlety.</p>
<p>I don't know a standard reference for this: I worked it out
for my own interest. However, it's an obvious enough construction that
I'm confident it's been invented before. Some casual Googling reveals
Joost Winter, Marcello Bonsangue and Jan Rutten's recent paper
<a href="http://oai.cwi.nl/oai/asset/18032/18032A.pdf" rel="nofollow noreferrer"><em>Context-Free Languages, Coalgebraically</em></a>, where they give a variant
of this definition (requiring all fixed points to be guarded) which
they also call context-free expressions.</p>

CC BY-SA 3.0
2014-08-28T13:06:11.260Z
Arto Salomaa covers this in his book “Formal Languages” in 1973. He calls them “Regular-like Expressions”.
Tim Schaeffer
CC BY-SA 4.0
2021-09-11T20:14:44.097Z
A related work is [Bart Gruppen's BSc thesis](https://www.cs.ru.nl/bachelors-theses/2018/Bart_Gruppen___4465784___From_mu-regular_expressions_to_CFGs_and_back.pdf) that proves the equivalence using grammars.  Gruppen refers Peter Thiemann's work ["Partial derivatives for context-free languages - from μ-regular expressions to pushdown automata."](https://arxiv.org/abs/1610.06832)
Tiago Cogumbreiro
CC BY-SA 4.0
2021-09-11T20:22:35.103Z
These are also known as μ-regular expressions. Hans Leiß defines it in [Towards Kleene Algebra with Recursion](https://www.cis.lmu.de/download/publikationen/kar_csl-91.pdf) in 1991. The links in my comment above refer to this as μ-regular expressions as well.
Tiago Cogumbreiro
CC BY-SA 4.0
2022-10-06T11:24:16.983Z
With this semantics the *"failing pattern"*, i.e. the empty language, also becomes definable as $\mu x.x$, no?
Martin Berger
CC BY-SA 4.0
2022-10-06T12:16:57.710Z
Yes, that's right.
Neel Krishnaswami
CC BY-SA 4.0
2013-03-17T13:45:33.630Z
2024-04-20T06:32:29.277Z
2024-04-20T06:32:29.277Z
Neel Krishnaswami
<p>In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example:</p>

<blockquote>
  <p>$S \to a a S b$<br>
  $S \to $</p>
</blockquote>

<p>generates $\{ a^{2i} b^i | i \geq 0\}$,</p>

<blockquote>
  <p>$S \to a S b$<br>
  $S \to a a S b$<br>
  $S \to $</p>
</blockquote>

<p>generates $\{ a^i b^j \mid i \geq j \geq 0 \}$, and</p>

<blockquote>
  <p>$S \to a S a$<br>
  $S \to b S b$<br>
  $S \to $</p>
</blockquote>

<p>generates $\{ w w^R \mid w \in (a|b)^* \}$, or equivalently $\{ ((a|b)^*)_1 ((a|b)^*)_2 \mid p_1 = p_2^R \}$ (where $p_1$ refers to the part captured by $(...)_1$).</p>

<p>The above examples can all be generated by adding indices ($a^i$), simple constraints on these indices ($i &gt; j$) and pattern matching to regular expressions. This makes me wonder whether all context-free languages can be generated by some extension of the regular expressions.</p>

<blockquote>
  <p>Is there an extension of regular expressions that can generate all of or some significant subset of the context free languages?</p>
</blockquote>

CC BY-SA 3.0
2013-03-17T11:18:30.360Z
Observe that adding indices and constraints is too powerful: you will be able to define $a^nb^nc^n$, which is not a CFL.
Shaull
<fl.formal-languages><context-free><context-free-languages>
Does there exist an extension of regular expressions that captures the context free languages?
Alex ten Brink
# Does there exist an extension of regular expressions that captures the context free languages?

(Asked by: username_0 on 2013-03-17)

In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example:

> $S \to a a S b$  
> $S \to $

generates $\{ a^{2i} b^i | i \geq 0\}$,

> $S \to a S b$  
> $S \to a a S b$  
> $S \to $

generates $\{ a^i b^j \mid i \geq j \geq 0 \}$, and

> $S \to a S a$  
> $S \to b S b$  
> $S \to $

generates $\{ w w^R \mid w \in (a|b)^\* \}$, or equivalently $\{ ((a|b)^\*)\_1 ((a|b)^\*)\_2 \mid p\_1 = p\_2^R \}$ (where $p\_1$ refers to the part captured by $(...)\_1$).

The above examples can all be generated by adding indices ($a^i$), simple constraints on these indices ($i > j$) and pattern matching to regular expressions. This makes me wonder whether all context-free languages can be generated by some extension of the regular expressions.

> Is there an extension of regular expressions that can generate all of or some significant subset of the context free languages?

**Tags:** fl.formal-languages, context-free, context-free-languages
> **Comments:**
> **username_1**: Observe that adding indices and constraints is too powerful: you will be able to define $a^nb^nc^n$, which is not a CFL.  

---

## 3 answers

### Answer by username_3 on 2013-03-17. Score: 42 | Accepted answer

Yes, there is. Define a *context-free expression* to be a term generated
by the following grammar:

$$
\begin{array}{lcll}
g & ::= & \epsilon & \mbox{Empty string}\\
& | & c & \mbox{Character $c$ in alphabet $\Sigma$} \\
& | & g \cdot g & \mbox{Concatenation} \\
& | & \bot & \mbox{Failing pattern} \\
& | & g \vee g & \mbox{Disjunction}\\
& | & \mu \alpha.\; g & \mbox{Recursive grammar expression} \\
& | & \alpha & \mbox{Variable expression}
\end{array}
$$

This is all of the constructors for regular languages except Kleene
star, which is replaced by a general fixed-point operator $\mu
\alpha.\;g$, and a variable reference mechanism. (The Kleene star is
not needed, since it can be defined as $g\ast \triangleq \mu
\alpha.\;\epsilon \vee g\cdot\alpha$.)

The interpretation of a context-free expression requires accounting
for the interpretation of free variables. So define an *environment*
$\rho$ to be a map from variables to languages (i.e., subsets of
$\Sigma^\*$), and let $[\rho|\alpha:L]$ be the function that behaves
like $\rho$ on all inputs except $\alpha$, and which returns the
language $L$ for $\alpha$.

Now, define the interpretation of a context-free expression as follows:

$$
\newcommand{\interp}[2]{[\![{#1}]\!]\;{#2}}
\newcommand{\setof}[1]{\left\{#1\right\}}
\newcommand{\comprehend}[2]{\setof{{#1}\;\mid|\;{#2}}}
\begin{array}{lcl}
\interp{\epsilon}{\rho} & = & \setof{\epsilon} \\
\interp{c}{\rho} & = & \setof{c} \\
\interp{g\_1\cdot g\_2}{\rho} & = & \comprehend{w\_1 \cdot w\_2}{w\_1 \in \interp{g\_1}{\rho} \land w\_2 \in \interp{g\_2}{\rho}} \\
\interp{\bot}{\rho} & = & \emptyset \\
\interp{g\_1 \vee g\_2}{\rho} & = & \interp{g\_1}{\rho} \cup \interp{g\_2}{\rho} \\
\interp{\alpha}{\rho} & = & \rho(\alpha) \\
\interp{\mu \alpha.\; g}{\rho} & = & \bigcup\_{n \in \mathbb{N}} L\_n \\
\mbox{where} & & \\
L\_0 & = & \emptyset \\
L\_{n+1} & = & L\_n \cup \interp{g}{[\rho|\alpha:L\_n]}
\end{array}
$$

Using the Knaster-Tarski theorem, it's easy to see that the
interpretation of $\mu \alpha.g$ is the least fixed of the expression.

It's straightforward (albeit not entirely trivial) to show that you
can give a context-free expression deriving the same language as any
context-free grammar, and vice-versa. The non-triviality arises from
the fact that context-free expressions have nested fixed points, and
context-free grammars give you a single fixed point over a tuple. This
requires the use of Bekic's lemma, which says precisely that a nested
fixed points can be converted to a single fixed point over a product (and
vice-versa). But that's the only subtlety.

I don't know a standard reference for this: I worked it out
for my own interest. However, it's an obvious enough construction that
I'm confident it's been invented before. Some casual Googling reveals
Joost Winter, Marcello Bonsangue and Jan Rutten's recent paper
[*Context-Free Languages, Coalgebraically*](http://oai.cwi.nl/oai/asset/18032/18032A.pdf), where they give a variant
of this definition (requiring all fixed points to be guarded) which
they also call context-free expressions.

> **Comments:**
> **username_5**: Arto Salomaa covers this in his book “Formal Languages” in 1973. He calls them “Regular-like Expressions”.  
> **username_6**: A related work is [Bart Gruppen's BSc thesis](https://www.cs.ru.nl/bachelors-theses/2018/Bart_Gruppen___4465784___From_mu-regular_expressions_to_CFGs_and_back.pdf) that proves the equivalence using grammars.  Gruppen refers Peter Thiemann's work ["Partial derivatives for context-free languages - from μ-regular expressions to pushdown automata."](https://arxiv.org/abs/1610.06832)  
> **username_6**: These are also known as μ-regular expressions. Hans Leiß defines it in [Towards Kleene Algebra with Recursion](https://www.cis.lmu.de/download/publikationen/kar_csl-91.pdf) in 1991. The links in my comment above refer to this as μ-regular expressions as well.  
> **username_7**: With this semantics the *"failing pattern"*, i.e. the empty language, also becomes definable as $\mu x.x$, no?  
> **username_3**: Yes, that's right.  

---

### Answer by username_2 on 2013-03-30. Score: 5

There was a closely related question (and several answers) on MathOverflow about the languages whose [generating functions are holonomic](https://mathoverflow.net/questions/8262/is-there-a-natural-family-of-languages-whose-generating-functions-are-holonomic).

Interestingly, Neel's definition of the semantics of $\mu$ above corresponds *exactly* to the (constructive) proof of the existence of Species solutions to recursive Species equations via the implicit Species theorem. Unfortunately, his proof outline must also contain a subtle mistake, as there are cases where things go 'infinite'. In other words, there is a condition on the Jacobian of the transformation defined by the grammar to be non-singular which is needed. This is probably why Bonsangue-Rutten require the fixed points to be guarded, as one way to insure this condition on the Jacobian.

> **Comments:**
> **username_3**: AFAICT, Winter et al only require guardedness in order to ensure you can take the Brzozowski derivative of $\mu\alpha.\;g$ by taking the derivative of $[\mu\alpha.\;g/\alpha]g$.  

---

### Answer by username_4 on 2024-04-18. Score: 0

Yes.

A simple example should suffice to show both what and how.

Consider the grammar given by
$$S → x,\quad S → u S v.$$
This specifies a subset of $\{u,x,v\}^\*$ and - more generally - a context-free subset of a monoid $M ⊇ \{u,x,v\}$ that may, but need not, be free. ([Context-Free Grammars Over Arbitrary Monoids](https://softwareengineering.stackexchange.com/questions/253454/what-does-context-free-mean-in-the-term-context-free-grammar/452893#452893)).

Extend $M$ with the inclusion of $Z = \{b,d,p,q\}$, subject to the identities $bd = 1 = pq$, $bq = 0 = pd$ and $mz = zm$, for $m ∈ M$ and $z ∈ Z$. Then we may write
$$S = b (u p)^\* x (q v)^\* d.$$

This is the contemporary form of an expression that would, in earlier times, have been arrived at by way of the [Chomsky-Schützenberger [Enumeration] Theorem](https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_enumeration_theorem), and the framework underlying it is an evolutionary descendant of this result

[The Algebraic Underpinning To Context-Free Expressions](https://math.stackexchange.com/questions/4843156/how-to-show-that-only-this-regular-expression-solves-this-equation/4890511#4890511)

[The Algebras And Categories Associated With Rational And Context-Free Subsets Of Monoids](https://cs.stackexchange.com/questions/42269/rational-subsets-of-a-monoid/167534#167534)

[An algebraic representation of the fixed-point closure of ∗-continuous Kleene algebras – A categorical Chomsky–Schützenberger theorem](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/B423ED951CD154761D1CCAE96A99BC4F/S0960129522000329a.pdf/an-algebraic-representation-of-the-fixed-point-closure-of-continuous-kleene-algebras-a-categorical-chomsky-schutzenberger-theorem.pdf)

Another example, that better illustrates the true nature and extent of this new framework, involves the following translation grammar
$$
E → u E v,\quad E → w E α,\quad E → E y E β,\quad E → x γ,\quad S → E z ω,
$$
which specifies a subset of $X^\* × Y^\*$, where $X = \{u,v,w,x,y,z\}$ and $Y = \{α,β,γ,ω\}$, or - more generally - a context-free subset of a monoid $M × N$, where $M ⊇ X$, $N ⊇ Y$ - may be given by a context-free expression corresponding to the following "linearization" of the above grammar:
$$
E\_0 → u ⟨1| E\_0,\quad E\_0 → w ⟨2| E\_0,\quad E\_0 → x γ E\_1,\\
E\_1 → y ⟨3| E\_0,\quad E\_1 → E\_2,\\
E\_2 → |0⟩ z ω,\quad E\_2 → |1⟩ v E\_1,\quad E\_2 → |2⟩ α E\_1,\quad E\_2 → |3⟩ β E\_1,\\
⟨0| E\_0
$$
with the last item being the top-level expression. Here, we may set
$$
⟨0| = bb,\quad ⟨1| = bp,\quad ⟨2| = pb,\quad ⟨3| = pp,\\
|0⟩ = dd,\quad |1⟩ = qd,\quad |2⟩ = dq,\quad |3⟩ = qq
$$
to capture the conditions $⟨i| |i⟩ = 1$ and $⟨i| |j⟩ = 0$ if $i ≠ j$; and we have, here, the identities:
$$x y = y x,\quad y z = z y,\quad z x = x z,\quad(x ∈ X,\quad y ∈ Y,\quad z ∈ Z),$$
along with $bd = 1 = pq$ and $bq = 0 = pd$. The corresponding context-free expression is
$$
⟨0| F (y ⟨3| F)^\* |0⟩ z ω,
$$
where
$$
F = (u ⟨1| + w ⟨2|)^\* x γ (|1⟩ v + |2⟩ α + |3⟩ β)^\*.
$$

If the grammar is thought of as a translation from prefix/infix order (with operators $w,y$ and brackets $u,v$) to postfix order (with operators $α,β$), then this is a context-free *translation* expression. When written as a linearized grammar, it may equally-well be interpreted as a parser that produces output "actions" $α,β,γ,ω$ and reads input "symbols" $u,v,w,x,y,z$.

It can be equally-well be written in a form that collates all of the $Y$ and $Z$ "actions" by merging $E\_1$ and $E\_2$ and factoring out $|2⟩ α + |3⟩ β$, rewriting the linearized grammar (with the aid of the commutativity relations on $X$, $Y$ and $Z$) as:
$$
E\_0 → u ⟨1| E\_0,\quad E\_0 → w ⟨2| E\_0,\quad E\_0 → x γ E\_1,\\
E\_1 → y G ⟨3| E\_0,\\
E\_1 → z G |0⟩ ω,\quad E\_1 → v G |1⟩ E\_1,\\
⟨0| E\_0
$$
and with the corresponding context-free expression:
$$⟨0| F (y G ⟨3| F)^\* z G ω |0⟩$$
where
$$F = (u ⟨1| + w ⟨2|)^\* x γ (v G |1⟩)^\*,\quad G = (|2⟩ α + |3⟩ β)^\*.$$

The pulling of the elements of $X$ out to the front, with commutativity, may be regarded as the algebraic form of a "look-ahead".


---

