patternMinor
Where in the Chomsky Hierarchy are Regular Expressions as a language?
Viewed 0 times
thehierarchyarewherechomskyregularexpressionslanguage
Problem
I'm referring to regular expressions as language: \begin{equation*}
\Sigma = \{ `
\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.
\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."
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.