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

Front Cover
Springer Science & Business Media, Apr 26, 2002 - Computers - 351 pages
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).
 

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

Finite State Transducers
163
Turing Machines as Computers
179
Further Reading
341
Copyright

Other editions - View all

Common terms and phrases

References to this book

Bibliographic information