1
$\begingroup$

I want to prove that the language of all regular expressions is not a regular language. I'm having trouble to approach this problem. I thought maybe to show that the parenthesis language is a part of it, and then I can rule out the regularity.

$\endgroup$
3
  • 1
    $\begingroup$ "The parenthesis language is a part of it". Have you thought about all regular expressions like $(^na)^n$? $\endgroup$
    – John L.
    May 10, 2022 at 14:10
  • 1
    $\begingroup$ A more interesting question might be about regular expressions in reverse polish notation where no parentheses is needed. $\endgroup$
    – John L.
    May 10, 2022 at 14:14
  • 1
    $\begingroup$ @JohnL. Hardly. $a^{n+1}+^n$. $\endgroup$ May 10, 2022 at 16:06

1 Answer 1

1
$\begingroup$

Yes, this will work: if you may assume that the language of matching brackets is non-regular, it suffices to know that whenever a language is regular, erasing all occurrences of a particular character from all of its words produces a regular language. That isn't very hard to prove.

$\endgroup$

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.