Or six? Or seven? This becomes clear once you think about it. If N/ is the regular expression for the machine that can cope with as many as n outstanding open left brackets then the regular expression for the machine that can cope with as many as n + 1 outstanding open left brackets is (0(N*)1)*
Back to notes