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 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 wL(G)) is much more complicated here than it is for regular languages. So is parsing, which involves not only membership, ...

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