Introduction to Languages, Machines and Logic : Computable Languages, Abstract Machines and Formal Logic (Paperback)

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 Multiplicatio