An introduction to formal languages and automata
By: Peter Linz
Edition: 4th ed.
Publisher: Narosa Pub. House
Published: 2007
Place of publication: New Delhi
Language: eng
Number of pages: 415
ISBN-13: 9788173197819
Subjects: Formal languages; Machine theory
Notes: Reprint. Originally published: Sudbury, Mass. : Jones and Bartlett Publishers, 2006.

Includes bibliographical references (page 409) and index.
Table of contents: title: Introduction to the theory of computation. mathematical preliminaries and notation ; Three basic concepts ; Some applications; title: Finite automata. Deterministic finite accepters ; Nondeterministic finite accepters; title: A hierarchy of formal languages and automata. Recursive and recursively enumerable languages ; Unrestricted grammars ; Context-sensitive grammars and languages ; The Chomsky hierarchy; title: Limits of algorithmic computation. Some problems that cannot be solved by Turing machines ; Undecidable problems for recursively enumerable languages ; The post correspondence problem ; Undecidable problems for context-free languages ; A question of efficiency; title: Other models of computation. Recursive functions ; Post systems ; Rewriting systems; title: An overview of computational complexity. Efficiency of computation ; Turing machine models and complexity ; Language families and complexity classes ; The complexity classes P and NP ; Some NP problems ; Polynomial-time reduction ; NP-completeness and an open question.