Limitations of Regular Expressions

Parentheses in expressions, statement blocks


The language of balanced (matched) parentheses (here: curly braces)

  • at each point count number of open minus number of closed parantheses
  • at every point the number must be non-negative
  • at the end the number must be zero

Is there a finite automaton describing balenced parentheses?

  • I wrote a finite state machine with 10'000 states and it seems to recognize balanced parantheses
  • Do I have a bug in my finite state machine? If so, can you tell me how to find it?

Pumping lemma for regular languages