Automata

This book presents the theory of formal languages as a coherent theory and makes explicit its relationship to automata. The book begins with an explanation of the notion of a finite description of a language. The fundamental descriptive device--the grammar--is explained, as well as its three major subclasses--regular, context-free, and context-sensitive grammars. The context-free grammars are treated in detail, and such topics as normal forms, derivation trees, and ambiguity are covered. Four types of automata equivalent to the four types of grammars are described.