[Solved]: Why is the set of all regular expressions classified as context-free, instead of regular?

Problem Detail: 

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?

Asked By : Helena Ng

Answered By : Klaus Draeger

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49551

3.2K people like this

 Download Related Notes/Documents