An Introduction to Formal Languages and Automata, 7th Edition

© VS148/Shutterstock.

CHAPTER 11A HIERARCHY OF FORMAL LANGUAGES AND AUTOMATA

CHAPTER SUMMARY

In this chapter, we study the connection between Turing machines and languages. Depending on how one defines language acceptance, we get several different language families: recursive, recursively enumerable, and context-sensitive languages. With regular and context-free languages, these form a properly nested relation called the Chomsky hierarchy.

We now return our attention to our main interest, the study of formal languages. Our immediate goal will be to examine the languages associated with Turing machines and some of their restrictions. Because ...