Automata and computability /

The aim of this textbook is to provide undergraduate students with an introduction to the basic theoretical models of computability, and to develop some of the model's rich and varied structure. Students who have already some experience with elementary discrete mathematics will find this a well...

Full description

Bibliographic Details
Main Author:	Kozen, Dexter, 1951-
Corporate Author:	SpringerLink (Online service)
Format:	eBook
Language:	English
Published:	New York : Springer, [1997]
Series:	Undergraduate texts in computer science.
Subjects:	Machine theory. Computable functions. machine Turing. langage algébrique. automate. calculabilité. fonction calculable. théorie machine. Fundamentele informatica. Abstracte automaten. Berekenbaarheid. Automatentheorie. Automates mathématiques, théorie des. Machines séquentielles, Théorie des. Complexité de calcul (informatique) Turing, Machines de. Kellerautomat. Kontextfreie Grammatik. Turing-Maschine. Berechenbarkeit. Endlicher Automat. Reguläre Menge. Electronic books.
Online Access:	Connect to the full text of this electronic book

Table of Contents:

1. Course Roadmap and Historical Perspective
2. Strings and Sets
3. Finite Automata and Regular Sets
4. More on Regular Sets
5. Nondeterministic Finite Automata
6. The Subset Construction
7. Pattern Matching
8. Pattern Matching and Regular Expressions
9. Regular Expressions and Finite Automata
A. Kleene Algebra and Regular Expressions
10. Homomorphisms
11. Limitations of Finite Automata
12. Using the Pumping Lemma
13. DFA State Minimization
14. A Minimization Algorithm
15. Myhill-Nerode Relations
16. The Myhill-Nerode Theorem
B. Collapsing Nondeterministic Automata
C. Automata on Terms
D. The Myhill-Nerode Theorem for Term Automata
17. Two-Way Finite Automata
18. 2DFAs and Regular Sets
19. Context-Free Grammars and Languages
20. Balanced Parentheses
21. Normal Forms
22. The Pumping Lemma for CFLs
23. Pushdown Automata
E. Final State Versus Empty Stack
24. PDAs and CFGs
25. Simulating NPDAs by CFGs
F. Deterministic Pushdown Automata
26. Parsing
27. The Cocke-Kasami-Younger Algorithm
G. The Chomsky-Schutzenberger Theorem
H. Parikh's Theorem
28. Turing Machines and Effective Computability
29. More on Turing Machines
30. Equivalent Models
31. Universal Machines and Diagonalization
32. Decidable and Undecidable Problems
33. Reduction
34. Rice's Theorem
35. Undecidable Problems About CFLs
36. Other Formalisms
37. The [lambda]-Calculus
I. While Programs
J. Beyond Undecidability
38. Godel's Incompleteness Theorem
39. Proof of the Incompleteness Theorem
K. Godel's Proof
Homework Sets
Miscellaneous Exercises
Hints and Solutions