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!

Improve this question
$\endgroup$
2
  • 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
    Commented Mar 3, 2018 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
    Commented Mar 3, 2018 at 23:25

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Nitpicking, that grammar does not generate the empty regular expression which generates the empty language. $\endgroup$
    – John L.
    Commented Dec 30, 2018 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.