Editing Computability (section)

=== Power of pushdown automata ===
Computer scientists define a language that can be accepted by a [[pushdown automaton]] as a '''[[Context-free language]]''', which can be specified as a '''[[Context-free grammar]]'''.  The language consisting of strings with equal numbers of 'a's and 'b's, which we showed was not a regular language, can be decided by a push-down automaton.  Also, in general, a push-down automaton can behave just like a finite-state machine, so it can decide any language which is regular.  This model of computation is thus strictly more powerful than finite state machines.

However, it turns out there are languages that cannot be decided by push-down automaton either.  The result is similar to that for regular expressions, and won't be detailed here.  There exists a [[Pumping lemma for context-free languages]].  An example of such a language is the set of prime numbers.