Problem on regular expression

Question

Let REGEXP be the language of valid regular expressions over {a, b}. That is, REGEXP is the set of all strings over the symbols Σ= {a, b, (,), U,*, ^} that are valid regular expressions. For example, the string “a (a U b)" is in REGEXP, whereas the string “U) a (" is not. Show that the language REGEXP is not regular.

Answer 1

We will prove using Pumping Lemma.

According to the Pumping Lemma if L is a regular language. Then there would exist three strings x, y, z such that

1) y! = ^
2) xy<=  N (N is no. of states of DFA)
3) xyⁿz is present in al for all n>=0.

Suppose REGEXP is a regular language.

Then consider the following observations :-

OBSERVATION:

A word in REGEX: -  a (a U b)
Consider x=a
y= (a
z=Ub)

Pumping the string y would make the following words:-
a (a (aU b)
a (a(a(a U b)
a (a (a (a (aU b)
And so on…. Which are no words in REGEX.

Conclusion: - The language cannot be pumped. Therefore it is not regular.