patternModerate
Why is the set of all regular expressions classified as context-free, instead of regular?
Viewed 0 times
whytheallfreeregularexpressionsinsteadcontextclassifiedset
Problem
As I understand regular languages can be closed under concatenation, so can I concatenate the set of all regular expressions to classify them as regular?
Solution
Going by the OP's comments, the real question here is not the one in the title, but "Why is the set of regular expressions a context-free (rather than regular) language?"
The reason is simply the occurrence of parentheses in more complex regular expressions like $(a+b)^b(a+c)^$. In order for such an expression to be well-formed, the parentheses must be balanced properly; this is one of the classical conditions which make a language non-regular (because a r.e. which begins with sufficiently many opening parentheses can always be pumped such that it becomes unbalanced).
The reason is simply the occurrence of parentheses in more complex regular expressions like $(a+b)^b(a+c)^$. In order for such an expression to be well-formed, the parentheses must be balanced properly; this is one of the classical conditions which make a language non-regular (because a r.e. which begins with sufficiently many opening parentheses can always be pumped such that it becomes unbalanced).
Context
StackExchange Computer Science Q#49551, answer score: 12
Revisions (0)
No revisions yet.