an introduction to the theory of computer science Sudkamp, Thomas A creator text bibliography mau Boston Pearson/Addison-Wesley c2006 2006 3rd ed monographic eng

print

xvii, 654 p. : ill. ; 25 cm Introduction -- Mathematical preliminaries -- Languages -- Context-free grammars -- Normal forms for context-free grammars -- Finite automata -- Properties of regular languages -- Pushdown automata and context-free languages -- Turing machines -- Turing computable functions -- The Chomsky hierarchy -- Decision problems and the Church-Turing thesis -- Undecidability -- Mu-recursive functions -- Time complexity -- P, np and cook's theorem -- Np-complete problems -- Additional complexity classes -- Parsing: an introduction -- Ll(k) grammars -- Lr(k) grammars Thomas A. Sudkamp Includes bibliographical references (p. 641-647) and indexes Formal languages Machine theory Computational complexity QA267.3 .S83 2006 511.3 STL 0321322215 (alk. paper) 2004030342 DLC 041221 20210307102841.0 57344192