I'm referring to regular expressions as language: \begin{equation*} \Sigma = \{ ``a", ``b", ``(", ``)", ``*", ... \} \end{equation*} and \begin{equation*} L = \Sigma^* \text{, which form a legal regular expression} \end{equation*} I am not referring to their computational power. I did some research, but wasn't able to find anything relevant. Intuitively, I would imagine they're context-free, but am not sure how to attempt a proof.

I am trying to use this as a lemma, so a reference, or recommendation for how to attempt a proof would be extremely helpful.


Are we talking regular expressions as in only union, concatenation and star?

Consider the following grammar:

$R -> a | b | c$

$R -> R+R$

$R -> RR$

$R -> R^*$

$R -> (R)$

This captures all regular expressions. So if we're only talking in the Chomsky hierarchy, then it's clearly context free. If you allow parentheses, it's not regular, since well-nested parentheses are known to not be regular. If you want a proof, do a homomorphism from the language of REs to the language of well-nested parentheses.

I don't know where they fit in terms of more detailed classification (i.e. $LL(1)$, $LR(0)$ etc.).

You could probably find something about this if you searched for "parsing regular expressions."

  • 1
    $\begingroup$ Yup, I'm only talking about regular expressions in the very formal sense (with union, concatenation and star). Very helpful answer, thank you very much! $\endgroup$ – Steve Peters Oct 15 '13 at 19:56

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.