note pKai <blockquote>The first two definitions are recursive, so they are not "regular" any more.</blockquote> <p>You can argue that the first production is "tail recursive" which does not pose a problem with respect to regularity. Like a tail recursive function can be transformed into a loop.</p> <p>The non-regularity comes with the 2nd production.</p> <blockquote><c>term -> '(' term ')'</c></blockquote> <p>The point is that <c>term</c> can grow to arbitrary length and we still should keep the correspondence between the two parentheses, which is not possible with (CS)-Regexes ("pumping lemma").<p> <p>This last observation is the border where you need a CFL-parser and would be lost with Regexes alone.</p> 678119 678119