2
$\begingroup$

so i know that the set of all strings over any finite alphabet is countable, but this question is different

so if our language is set of all regular languages(or set of all regular expressions) on a specific and finite alphabet, then is this set regular? if not then what is it? CFL?

i really can't come up with any FA that can accept this!

$\endgroup$
  • 1
    $\begingroup$ The set of all regular languages is a set of sets of strings; a language is a set of strings. Therfore, a set of languages can't itself be a language. $\endgroup$ – David Richerby Mar 3 '18 at 23:17
  • 1
    $\begingroup$ Regular languages and regular expressions are different things. The latter are descriptions of the former. For instance, different expressions can describe the same language. $\endgroup$ – reinierpost Mar 3 '18 at 23:25
3
$\begingroup$

The language of regular expressions is context-free, but not regular. It is given by the following grammar:

$$E ::= 0 | 1 | (E)^* | E E | (E|E)$$

Because of the parenthesis matching effect, it's not regular -- the language of matched parentheses is not regular.

$\endgroup$
  • $\begingroup$ Nitpicking, that grammar does not generate the empty regular expression which generates the empty language. $\endgroup$ – Apass.Jack Dec 30 '18 at 6:23

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.