000 03846cam 2200421 a 4500
001 278540
005 20080605110323.0
008 071220s2006 maua b 001 0 eng
010 $a 2005032046
020 $a0763737984 (casebound)
020 $a9780763737986 (casebound)
024 $a99818765944
029 1 $aYDXCP$b2264820
029 1 $aNLGGC$b292105487
029 1 $aNZ1$b10559311
035 $a(OCoLC)ocm62282001
035 $a(OCoLC)62282001
035 $a278540
040 $aDLC$cDLC$dYDX$dBAKER$dBTCTA$dYDXCP$dNLGGC
049 $aWPGG
050 00 $aQA267.3$b.L56 2006
082 00 $a005.13/1$222
084 $a54.10$2bcl
100 1 $aLinz, Peter.
245 13 $aAn introduction to formal languages and automata
/$cPeter Linz.
250 $a4th ed.
260 $aSudbury, Mass. :$bJones and Bartlett
Publishers,$cc2006.
300 $axiii, 415 p. :$bill. ;$c25 cm.
504 $aIncludes bibliographical references (p. 409) and
index.
505 2 $aIntroduction to the Theory of Computation --
Mathematical Preliminaries and Notation -- Three Basic
Concepts -- Some Applications -- Finite Automata :
Deterministic Finite Accepters -- Nondeterministic Finite
Accepters -- Equivalence of Deterministic and
Nondeterministic Finite Accepters -- Reduction of the
Number of States in Finite Automata -- Regular Languages and
Regular Grammars : Regular Expressions -- Connection Between
Regular Expressions and Regular Languages -- Regular
Grammars -- Properties of Regular Languages : Closure
Properties of Regular Languages -- Elementary Questions
about Regular Languages -- Identifying Nonregular Languages
-- Context-Free Languages : Context-Free Grammars -- Parsing
and Ambiguity -- Context-Free Grammars and Programming
Languages -- Simplification of Context-Free Grammars and
Normal Forms : Methods for Transforming Grammas -- Two
Important Normal Forms -- A Membership Algorithm for
Context-Free Grammars* -- Pushdown Automata :
Nondeterministic Pushdown Automata -- Pushdown Automata and
Context-Free Languages -- Deterministic Pushdown Automata
and Deterministic -- Grammars for Deterministic Context-Free
Languages* -- Properties of Context-Free Languages : Two
Pumping Lemmas -- Closure Properties and Decision Algorithms
for Context-Free Languages -- Turing Machines : The Standard
Turing Machine -- Combining Turing Machines for Complicated
Tasks -- Turing's Thesis -- Other Models of Turing Machines
: Minor Variations on the Turing Machine Theme -- Turing
Machines with More Complex Storage -- Nondeterministic
Turing Machines -- A Universal Turing Machine -- Linear
Bounded Automata -- A Hierarchy of Formal Languages And
Automata : Recursive and Recursively Enumerkble Languages --
Unrestricted Grammars -- Context-Sensitive Grammars and
Languages -- The Chomsky Hierarchy -- 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 -- Other Models of Computation : Recursive
Functions -- Post Systems -- Rewriting Systems -- 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.
650 0 $aFormal languages.
650 0 $aMachine theory.
856 41 $3Table of contents
only$uhttp://www.loc.gov/catdir/toc/fy0607/2005032046.html
938 $aBaker and Taylor$bBTCP$n2005032046
938 $aYBP Library Services$bYANK$n2264820
938 $aBaker & Taylor$bBKTY$c109.95$d109.95$i0763737984$
n0006625527$sactive
949 $aGEN$bBKSP$iA17903054933
994 $a92$bWPG
