CHAPTER 5
CONTEXT-FREE LANGUAGES
CHAPTER SUMMARY
Having discovered the limitations of regular languages, now we go on to study more complicated languages by defining a new type of grammar, context-free grammars, and associated context-free languages. While context-free grammars are still fairly simple, they can deal with some of languages that we know are not regular. This tells us that the family of regular languages is a proper subset of the family of context-free languages.
Two important concepts encountered here are the membership question and parsing: The membership problem (given a grammar G and a string w, find if w ∈ L(G)) is much more complicated here than it is for regular languages. So is parsing, which involves not only membership, ...
Get An Introduction to Formal Languages and Automata, 6th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
