PrefacetotheFirstEdition
Tothestudent
Totheeducator
Thefirstedition
Feedbacktotheauthor
Acknowledgments
PrefacetotheSceondEdition(International)
0Introduction
0.1Automata,CompUTABILITY,andComplexity
Complexitytheory
Computabilitytheory
0.2MathematicalNotionsandTerminology
Sets
Sequemcesandtuples
Functionsandrelations
Graphs
Stringsandlanguges
Booleanlogic
Summaryofmathematicalterms
0.3Definitions,Theorems,andProofs
Findingproofs
0.4TypesofProof
Proofbyconstruction
Proofbyconstruction
Proofbyinduction
Exercises,Problims,andSolutions
PartOne:AutomataandLanguages
1RegularLanguages
1.1FiniteAutomata
Formaldefinitionofafiniteautomaton
Examplesoffiniteautomata
Formaldefinitionofcomputation
Designignfiniteautomata
Theregularoperations
1.2Nondeteriminism
Formaldefinitionofanondeterministicfiniteautomaton
EquivalenceofNFAsandDFAs
Closureundertheregularoperations
1.3RegularExpressions
Formaldefinitionofaregularexpression
Equivalencewithfiniteautomata
1.4NonregularLanguages
Thepumpinglemmaforregulanlanguages
Exercises,Problems,andSolutions
2Context-FreeLanguages
2.1Conetxt-freeGrammars
Formaldefinitionofacontext-freegrammar
Examplesofcontext-freegrammars
Designingcontext-freegrammars
Ambiguity
Chomakymormalform
2.2PushdownAutomata
Formaldefinitionofapushdownautomaton
Examplesofpushdownautonata
Equivalencewishcontext-freegrammars
2.3Non-context-freeLanguages
Thepumpinglemmaforcontext-freelanguages
Exercises,Problems,andSolutions
PartTwo:ComputabilityTheory
PartThree:ComputabilityTheory
SelectedBibliography
Index