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

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?

• 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 Mar 17 '13 at 11:18

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}{[\![{#1}]\!]\;{#2}} \newcommand{\setof}{\left\{#1\right\}} \newcommand{\comprehend}{\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.

• This is pretty awesome. Is there a standard name or reference for this? – Alex ten Brink Mar 17 '13 at 19:10
• Arto Salomaa covers this in his book “Formal Languages” in 1973. He calls them “Regular-like Expressions”. – Tim Schaeffer Aug 28 '14 at 13:06

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.

• 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 Mar 31 '13 at 19:33

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.

• Please include all relevant information in the answer itself. “Look under comp.compilers” is an unhelpul answer already now, and it will be completely useless in a couple of months. – Emil Jeřábek Nov 15 '18 at 7:32
• That's totally wrong. Comp.compilers (unlike this site and other blogs, by the way) is permanently archived. There you will find all the details you need. There are many links that may be found there, in the most recently posted article, as well. Also, unlike blog sites, it is open to the outside and useful to a much wider audience. You should have no difficulty finding anything on the USENET - which is where queries like this should be addressed and discussed. If you have difficulty, here is the link. groups.google.com/forum/#!topic/comp.compilers/YCa5jHUR1iQ – NinjaDarth Nov 16 '18 at 21:38
• The issue is not that it is not archived, but that the archives are vast. When I look up the archives now I can find your post somewhere near the top, but when someone will see this answer a few months or years into the future, they will have no idea where to start digging. It is arrogant and rude to make the readers do a lengthy and unreliable search when you can point them to a more specific location. Now, I did it for you. It took like 30 seconds. You could have done that yourself. – Emil Jeřábek Nov 19 '18 at 18:58