CHAPTER 8
PROPERTIES OF CONTEXT-FREE LANGUAGES
CHAPTER SUMMARY
In this chapter, we study the general properties for context-free languages to compare with what we know about the properties of regular languages. We see here that when it comes to closure and decision algorithms, these properties tend to be more complicated for context-free languages. This is especially true for the two pumping lemmas, one for context-free languages, the other for linear languages. While the basic idea is the same as for regular languages, specific arguments normally involve much more detail.
The family of context-free languages occupies a central position in a hierarchy of formal languages. On the one hand, context-free languages include important but restricted ...
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.
