A well-written and accessible introduction to the most important features of formal languages and automata theory. It focuses on the key concepts, illustrating potentially intimidating material through diagrams and pictorial representations, and this edition includes new and expanded coverage of topics such as: reduction and simplification of material on Turing machines; complexity and O notation; propositional logic and first order predicate logic. Aimed primarily at computer scientists rather than mathematicians, algorithms and proofs are presented informally through examples, and there are numerous exercises (many with solutions) and an extensive glossary.

Inhalt

1 Introduction.- Overview.- What This Book Is About.- What This Book Tries to Do.- What This Book Tries Not to Do.- The Exercises.- Further Reading.- Some Advice.- 1 Languages and Machines.- 2 Elements of Formal Languages.- Overview.- Alphabets.- Strings.- Functions that Apply to Strings.- Useful Notation for Describing Strings.- Formal Languages.- Methods for Defining Formal Languages.- Set Definitions of Languages.- Decision Programs for Languages.- Rules for Generating Languages.- Formal Grammars.- Grammars, Derivations, and Languages.- The Relationship Between Grammars and Languages.- Phrase Structure Grammars and the Chomsky Hierarchy.- Formal Definition of PSGs.- Derivations, Sentential Forms, Sentences, and "L(G)".- The Chomsky Hierarchy.- A Type 0 Grammar: Computation as Symbol Manipulation.- Exercises.- 3 Syntax, Semantics, and Ambiguity.- Overview.- Syntax Vs. Semantics.- Derivation Trees.- Parsing.- Ambiguity.- Exercises.- 4 Regular Languages and Finite State Recognisers.- Overview.- Regular Grammars.- Some Problems with Grammars.- Finite State Recognisers and Finite State Generators.- Creating an FSR.- The Behaviour of the FSR.- The FSR as Equivalent to the Regular Grammar.- Non-determinism in FSRs.- Constructing Deterministic FSRs.- The DFSR as Equivalent to the Non-DFSR.- A Simple Deterministic Decision Program.- Minimal FSRs.- Constructing a Minimal FSR.- Why Minimisation Works.- The General Equivalence of Regular Languages and FSRs.- Observations on Regular Grammars and Languages.- Exercises.- 5 Context Free Languages and Pushdown Recognisers.- Overview.- Context Free Grammars and Context Free Languages.- Changing G Without Changing L(G).- The Empty String (?).- Chomsky Normal Form.- Pushdown Recognisers.- The Stack.- Constructing a Non-deterministic PDR.- Example NPDRs,M3 and M10.- Deterministic PDRs.- M3d, a Deterministic Version of M3.- More DPDRs.- Deterministic and Non-deterministic CFLs.- Every Regular Language Is a Deterministic CFL.- The Non-deterministic CFLs.- A Refinement to the Chomsky Hierarchy in the.- Case of CFLs.- The Equivalence of the CFLs and the PDRs.- Observations on CFGs and CFLs.- Exercises.- 6 Important Features of Regular and Context Free Languages.- Overview.- Closure Properties of Languages.- Closure Properties of the Regular Languages.- Complement.- Union.- Intersection.- Concatenation.- Closure Properties of the Context Free Languages.- Union.- Concatenation.- Intersection.- Complement.- Chomsky's Hierarchy Is Indeed a Proper Hierarchy.- The "Repeat State Theorem".- A Language that Is Context Free but Not Regular.- The"uvwxy" Theorem for CFLs.- {aibici:i?1} Is Not Context Free.- The "Multiplication Language" Is Not Context Free.- Preliminary Observations on the Scope of the Chomsky Hierarchy.- Exercises.- 7 Phrase Structure Languages and Turing Machines.- Overview.- The Architecture of the Turing Machine.- "Tapes" and the "Read/Write Head".- Blank Squares.- TM "Instructions".- TMs Defined.- The Behaviour of a TM.- TMs as Language Recognisers.- Regular Languages.- Context Free Languages.- TMs Are More Powerful than PDRs.- to (TM) Computable Languages.- The TM as the Recogniser for the Context Sensitive Languages.- Constructing a Non-deterministic TM for Reduction Parsing of a Context Sensitive Language.- The Generality of the Construction.- The TM as the Recogniser for the Type 0 Languages.- Amending the Reduction Parsing TM to Deal with Type 0 Productions.- Dealing with the Empty String.- The TM as the Recogniser for All Types in the Chomsky Hierarchy.- Decidability: A Preliminary Discussion.- Deciding a Language.- Accepting a Language.- End of Part 1.- Exercises.- 2 Machines and Computation.- 8 Finite State Transducers.- Overview.- Finite State Transducers.- FSTs and Language Recognition.- FSTs and Memory.- FSTs and Computation.- Simple Multiplication.- Addition and Subtraction.- Simple Division and Modular Arithmetic.- The Limitations of the FST.- Restricted FST Multiplication.- FSTs and Unlimited Multiplication.- FSTs as Unsuitable Models for Real Computers.- Exercises.- 9 Turing Machines as Computers.- Overview.- Turing Machines and Computation.- TMs and Arbitrary Binary Multiplication.- Some Basic TM Operations.- The "ADD" TM.- The "MULT" TM.- TMs and Arbitrary Integer Division.- The "SUBTRACT" TM.- The "DIV" TM.- Logical Operations.- TMs and the Simulation of Computer Operations.- Exercises.- 10 Turing's Thesis and the Universality of the Turing Machine.- Overview.- Turing's Thesis.- Coding a TM and Its Tape as a Binary Number.- Coding Any TM.- Coding the Tape.- The Universal Turing Machine.- UTM's Tapes.- The Operation of UTM.- Some Implications of UTM.- Non-deterministic TMs.- Converting a Non-deterministic TM into a 4-tape Deterministic TM.- The Four Tapes of the Deterministic Machine, D.- The Systematic Generation of the Strings of Quintuple Labels.- The Operation of D.- The Equivalence of Non-deterministic and Four-tape Deterministic TMs.- Converting a Multi-tape TM into a Single-tape TM.- Example: Representing Three Tapes as One.- The Operation of the Single-tape Machine, S.- The Equivalence of Deterministic Multi-tape and Deterministic Single-tape TMs.- The Linguistic Implications of the Equivalence of Non-deterministic and Deterministic TMs.- Exercises.- 11 Computability, Solvability, and the Halting Problem.- Overview 231.- The Relationship Between Functions, Problems, Solvability, and Decidability.- Functions and Computability.- Problems and Solvability.- Decision Problems and Decidability.- The Halting Problem.- UTMHPartially Solves the Halting Problem.- Reductio ad Absurdum Applied to the Halting Problem.- The Halting Problem Shown to Be Unsolvable.- Some Implications of the Unsolvability of the Halting Problem.- Computable Languages.- An Unacceptable (Non-computable) Language.- An Acceptable, but Undecidable, Language.- Languages and Machines.- Exercises.- 12 Dimensions of Computation.- Overview.- Aspects of Computation: Space, Time, and Complexity.- Non-deterministic TMs Viewed as Parallel Processors..- Parallel Computations and Time.- A Brief Look at an Unsolved Problem of Complexity..- A Beginner's Guide to the "Big 0".- Predicting the Running Time of Algorithms.- Linear Time.- Logarithmic Time.- Polynomial Time.- Exponential Time.- The Implications of Exponential Time Processes.- Is P Equal to NP?.- Observations on the Efficiency of Algorithms.- End of Part 2.- Exercises.- 3 Computation and Logic.- 13 Boolean Logic and Propositional Logic.- Overview.- Boolean Logic.- Boolean Logic Operators.- Boolean Logic for Problem Solving.- Boolean Logic and Computing.- Propositional Logic.- Propositions.- Implication and Equivalence.- Rules of Inference.- Problem Solving and Reasoning in Propositional Logic.- Using Truth Tables to Prove Things in Propositional Logic.- Observations on Propositional Logic.- Exercises.- 14 First Order Predicate Logic.- Overview.- Predicate Logic.- Predicates.- Functions.- "Sentences" Revisited: Well-formed Formulae.- The "First Orderness" of First Order Logic.- Quantifiers.- The Existential Quantifier.- The Universal Quantifier.- A "Blocks World" Example of FOPL Representation.- The Semantics of FOPL: Interpretation.- Problem Solving and Inference in FOPL.- Rules of Inference for FOPL…