O'Reilly logo

An Introduction to Formal Languages and Automata, 6th Edition by Linz

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required