So I was wondering something about the Chomsky hierarchy.

DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages.

Right-regular or left-regular grammars produce regular languages, while context-free grammars produce context-free languages.

Regular expressions represent regular languages - but is there a context-free equivalent? i.e. is there some additional term we could allow to appear in a regular expression such that regular expressions with that functionality now represent context-free languages?


A (rather technical) answer, where star-operator is replaced by least fixed point (equivalent to recursive formulation as in CFG) is given by our cstheory cousins: Does there exist an extension of regular expressions that captures the context free languages?

The author (Neel Krishnaswami) of that answer does not know an original source of his construction, but a later comment by Tim Schaeffer refers to the 1973 book Formal Languages by Arto Salomaa. In chapter VI.11 Salomaa introduces regular-like expressions. That book might not be in your possession, but in turn refers to A characterization of context-free languages, Journal of Computer and System Sciences, 1973, by Jozef Gruska, which is open access.

The operator Gruska considers is the following, I loosely quote from his paper. Let $\sigma$ be a symbol and $L,L_1$ be languages. The $\sigma$-substitution of $L_1$ into $L$, denoted by $L \overset{\sigma}{\uparrow}L_1$ is defined by

$$ L \overset{\sigma}{\uparrow}L_1 = \{ x_0 y_1x_1 \dots x_{k-1} y_k x_k \mid x_0 \sigma x_1 \dots x_{k-1} \sigma x_k\in L, \text{no $\sigma$ in }x_i, y_i\in L_1 \}.$$

After noting that he operation $\overset{\sigma}{\uparrow}$ is associative one defines the $\sigma$-iteration as

$$ L^\sigma = \{z \mid z\in L \cup L\overset{\sigma}{\uparrow}L \cup L\overset{\sigma}{\uparrow}L\overset{\sigma}{\uparrow}L \cup \dots \text{ does not contain an occurrence of } \sigma \}.$$

Note that if we have only a single variable, like $S\to aSbS \mid \lambda$ then this substitution closure $\{aSbS, \lambda\}^S$ is indeed the language generated by the grammar.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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