Introduction to Languages, Machines and Logic
Computable Languages, Abstract Machines and Formal Logic
(Sprache: Englisch)
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...
Leider schon ausverkauft
versandkostenfrei
Buch (Kartoniert)
74.85 €
37 DeutschlandCard Punkte
sammeln
- Lastschrift, Kreditkarte, Paypal, Rechnung
- Kostenlose Rücksendung
- Ratenzahlung möglich
Produktdetails
Produktinformationen zu „Introduction to Languages, Machines and Logic “
Klappentext zu „Introduction to Languages, Machines and Logic “
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).
This book provides an accessible introduction to the most important features of formal languages and automata theory - core topics on computer science degree schemes worldwide. It focuses on the key concepts, illustrating potentially intimidating material through diagrams and pictorial representations, and this edition will include 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. This book will be invaluable to students of computer science but it will also prove essential reading to all practitioners needing to know about formal methods.
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. This book will be invaluable to students of computer science but it will also prove essential reading to all practitioners needing to know about formal methods.
Inhaltsverzeichnis zu „Introduction to Languages, Machines and Logic “
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
... mehr
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
- 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
... weniger
Bibliographische Angaben
- Autor: Alan P. Parkes
- 2002, XI, 351 Seiten, Maße: 23,5 cm, Kartoniert (TB), Englisch
- Verlag: Springer, Berlin
- ISBN-10: 1852334649
- ISBN-13: 9781852334642
Sprache:
Englisch
Pressezitat
From the reviews: "The book is accessible to students with limited mathematical training ... . The text is illustrated with nice pictures; there are many exercises and some of them have sketchy solutions grouped in a special section. The book also includes comments on further readings and a good index." (Cristian S. Calude, Zentralblatt MATH, Vol. 1041 (16), 2004)
Kommentar zu "Introduction to Languages, Machines and Logic"
0 Gebrauchte Artikel zu „Introduction to Languages, Machines and Logic“
| Zustand | Preis | Porto | Zahlung | Verkäufer | Rating |
|---|
Schreiben Sie einen Kommentar zu "Introduction to Languages, Machines and Logic".
Kommentar verfassen