29
$\begingroup$

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?

$\endgroup$
1
  • 6
    $\begingroup$ Observe that adding indices and constraints is too powerful: you will be able to define $a^nb^nc^n$, which is not a CFL. $\endgroup$
    – Shaull
    Commented Mar 17, 2013 at 11:18

3 Answers 3

42
$\begingroup$

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, where they give a variant of this definition (requiring all fixed points to be guarded) which they also call context-free expressions.

$\endgroup$
5
5
$\begingroup$

There was a closely related question (and several answers) on MathOverflow about the 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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ Commented Mar 31, 2013 at 19:33
0
$\begingroup$

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).

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, and the framework underlying it is an evolutionary descendant of this result

The Algebraic Underpinning To Context-Free Expressions

The Algebras And Categories Associated With Rational And Context-Free Subsets Of Monoids

An algebraic representation of the fixed-point closure of ∗-continuous Kleene algebras – A categorical Chomsky–Schützenberger theorem

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.