**You are here:**

# Introduction to Languages, Machines and Logic: Computable Languages, Abstract Machines and Formal…

## byAlan P. Parkes

### Paperback | April 26, 2002

### Pricing and Purchase Info

$110.65 online

$117.50 list price save 5%

Earn 553 plum

^{®}pointsPrices and offers may vary in store

### about

1.1 Overview This chapter briefly describes: • what this book is about • what this book tries to do • what this book tries not to do • a useful feature of the book: the exercises. 1.2 What This Book Is About This book is about three key topics of computer science, namely computable lan guages, abstract machines, and logic. Computable languages are related to what are usually known as "formal lan guages". I avoid using the latter phrase here because later on in the book I distin guish between formal languages and computable languages. In fact, computable languages are a special type of formal languages that can be processed, in ways considered in this book, by computers, or rather abstract machines that represent computers. Abstract machines are formal computing devices that we use to investigate prop erties of real computing devices. The term that is sometimes used to describe abstract machines is automata, but that sounds too much like real machines, in particular the type of machines we call robots. The logic part of the book considers using different types of formal logic to represent things and reason about them. The logics we consider all play a very important role in computing. They are Boolean logic, propositional logic, and first order predicate logic (FOPL).

### Details & Specs

Title:Introduction to Languages, Machines and Logic: Computable Languages, Abstract Machines and Formal…Format:PaperbackPublished:April 26, 2002Publisher:Springer-Verlag/Sci-Tech/TradeLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:1852334649

ISBN - 13:9781852334642

### Customer Reviews of Introduction to Languages, Machines and Logic: Computable Languages, Abstract Machines and Formal Logic

### Extra Content

Table of Contents

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.- Solving Problems by Classical FOPL Reasoning.- The Nature of FOPL.- Conclusions.- Exercises.- 15 Logic and Computation.- Overview.- A Computational Form of FOPL.- Getting Rid of ?.- Getting Rid of ?.- Conjunctive Normal Form Databases.- Resolution.- The Role of Unification in Resolution.- How to Do Resolution.- The Efficiency of Resolution.- Why Resolution Works.- Logic in Action.- Languages, Machines, and Logic.- Exercises.- Solutions to Selected Exercises.- 2.- 3.- 4.- 5.- 6.- 7.- 8.- 9.- 10.- 11.- 12.- 13.- 14.- 15.- Further Reading.

Editorial Reviews