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?
Does there exist an extension of regular expressions that captures the context free languages?
fl.formal languages;context free;context free languages
Yes, there is. Define a context-free expression to be a term generatedby 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 Kleenestar, which is replaced by a general fixed-point operator $\mu\alpha.\;g$, and a variable reference mechanism. (The Kleene star isnot 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 accountingfor 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 behaveslike $\rho$ on all inputs except $\alpha$, and which returns thelanguage $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 theinterpretation of $\mu \alpha.g$ is the least fixed of the expression.It's straightforward (albeit not entirely trivial) to show that youcan give a context-free expression deriving the same language as anycontext-free grammar, and vice-versa. The non-triviality arises fromthe fact that context-free expressions have nested fixed points, andcontext-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 (andvice-versa). But that's the only subtlety. EDIT: No, I don't know a standard reference for this: I worked it outfor my own interest. However, it's an obvious enough construction thatI'm confident it's been invented before. Some casual Googling revealsJoost Winter, Marcello Bonsangue and Jan Rutten's recent paperContext-Free Languages, Coalgebraically, where they give a variantof this definition (requiring all fixed points to be guarded) whichthey also call context-free expressions.