## Introduction to Languages, Machines and Logic: Computable Languages, Abstract Machines and Formal Logic1.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). |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

Languages and Machines | 11 |

Syntax Semantics and Ambiguity | 37 |

Regular Languages and Finite State Recognisers | 49 |

Context Free Languages and Pushdown Recognisers | 81 |

Deterministic PDRs | 96 |

Important Features of Regular and Context | 107 |

Phrase Structure Languages and Turing Machines | 133 |

Turings Thesis and the Universality of | 203 |

Computability Solvability and the Halting Problem | 231 |

Dimensions of Computation | 249 |

Boolean Logic and Propositional Logic | 275 |

First Order Predicate Logic | 291 |

Logic and Computation | 307 |

Solutions to Selected Exercises | 327 |

Chapter 6 | 333 |

### Other editions - View all

Introduction to Languages, Machines and Logic: Computable Languages ... Alan P. Parkes Limited preview - 2012 |

### Common terms and phrases

abstract machines accepted alphabet applied array assume binary number blank square Boolean logic called Chapter Chomsky hierarchy clauses concatenated configuration conjunctive normal form consider construction context free context sensitive copy database defined derivation tree deterministic CFLs deterministic machine deterministic TM DFSR digit discussion DPDR empty string equivalent exercises expression finite state recogniser followed FOPL statement formal languages function given goto halting problem input string input symbol input tape labelled left-hand side loop marker MULT non-deterministic TM non-terminals NPDR operations output PARSE TREE Pascal predicate predicate logic productions programming language PROLOG propositional logic read/write head regular grammar regular languages replace representation represented result right-hand side sentence sentential form shown in Figure shows simply single-tape solution solve specified stack strings of length subset algorithm syntax tape square terminal string terminal symbols theorem transition true truth table Turing machine uvwxy