Does there exist an extension of regular expressions that captures the context free languages?

Question

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?

Answer 1

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.

EDIT: No, 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.

Answer 2

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.

Answer 3

We've recently published the outlines of a framework that will do just that. Look under comp.compilers, where I sent a notification along with some links.

The new developments work off the Chomsky-Schuetzenberger Theorem and may be regarded as a completion of this result. Chomsky, himself, has been apprised of the developments and indicates a desire to "catch up".

Along with this development, we also establish the equivalence of two separate formulations for context-free expressions -- one which is an extension/completion of the "least fixed point" mu-calculus form (originally by Gruska, Yntema and McWhirter) -- which received a final formulation of sorts in 2014 -- and the other published in 2008.