Suppose the balanced braces language were a regular language. Since it's infinite, we may use the pumping lemma, after modifying it to our nefarious ends. Suppose the balanced braces language were regular. Examining the proof of that lemma, we see that we may take the decomposition w=xyz with y contained in any subword of w of size >= k, where k is the number of states in a finite state automaton recognising the balanced braces language. (Proving this variant of the pumping lemma is left as an exercise to the reader).

That's enough for us. Consider the word w consisting of k opening braces followed by k closing braces: "(((...)))". Applying our modified pumping lemma to the first k letters of w, we see that w=xyz, with x,y consisting solely of opening braces. Then we know xy^2z is also in the language, which is clearly impossible -- it contains |y| more open braces than close braces!

It's also possible to prove this fact using the Myhill / Nerode theorem; see the Myhill theorem proof that the balanced braces language is not regular.

Log in or register to write something here or to contact authors.