[antlr-interest] Regular Expression vs CFG

[Oliver Wong]

> On Monday 05 March 2007 18:29, Dennis Katumalla wrote:
> > Can someone give me a simple example where a regular expression
> > alone (using java.util.regex) is not sufficient to parse a SQL
> > statement and requires specification of a full grammar?
>
> The mere fact that there are balanced and nested constructs
> (e.g., parenthesized sub-expressions) is enough to tell you that
> no finite automaton alone can recognize the language. Such
> constructs demand a push-down automaton of some sort.

For more information on this, google for "Pumping Lemma". In particular:
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

	- Oliver