Consider the words

w1 = "(",
w2 = "((",
...,
wn = "("n,
...
(wn is n open braces). Then, using the notation of the Myhill / Nerode theorem, S(wn) is different for each n: it contains ")"n, but no other string of only close braces). Thus there are infinitely many types for S(w), so by the Myhill / Nerode Theorem the balanced braces language is not a regular language.

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