HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Where in the Chomsky Hierarchy are Regular Expressions as a language?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thehierarchyarewherechomskyregularexpressionslanguage

Problem

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.

Solution

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."

Context

StackExchange Computer Science Q#16109, answer score: 3

Revisions (0)

No revisions yet.