An Introduction to Formal Languages and Automata, 7th Edition

© VS148/Shutterstock.

CHAPTER 6SIMPLIFICATION OF CONTEXT-FREE GRAMMARS AND NORMAL FORMS

CHAPTER SUMMARY

In Chapter 5, we encountered the important issues of membership and parsing for context-free languages. While brute force parsing is always possible, it is very inefficient and therefore not practical. For actual applications, such as compilers, we need more efficient methods. This is made difficult by the unrestricted form of the right side of a context-free production, so we investigate if we can restrict the right side without reducing the power of the grammar.

The first thing we can do is to show that we need not worry about certain ...