next up previous contents
Next: halting digression Up: Ben's presentation Previous: Ben's presentation

Properties of context-free languages

The pumping lemma for context-free languages is not as powerful as the pumping lemma for FAs. Once you move into CFGs, you run into the halting problem. You can't tell if a CFG will accept a given language, as you can with an FA.