Skip to main content
SpringerLink
Log in

Introduction to Languages, Machines and Logic

Computable Languages, Abstract Machines and Formal Logic

  • Textbook
  • © 2002

Overview

Authors:
  1. Alan P. Parkes

    1. Distributed Multimedia Research Group, Computing Department, Lancaster University, Lancaster

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • AN INFORMAL AND ACCESSIBLE INTRODUCTION TO POTENTIALLY INTIMIDATING CONCEPTS READER-FRIENDLY, NON-MATHEMATICAL PRESENTATION INCLUDES NUMEROUS EXERCISES (MANY WITH SOLUTIONS) AND AN EXTENSIVE GLOSSARY
  • Includes supplementary material: sn.pub/extras

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 59.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (15 chapters)

  1. Front Matter

    Pages i-xi
    Download chapter PDF

  2. Introduction

    1. Introduction

      • Alan P. Parkes
      Pages 1-7

  3. Languages and Machines

    1. Front Matter

      Pages 9-9
      Download chapter PDF

    2. Elements of Formal Languages

      • Alan P. Parkes
      Pages 11-36

    3. Syntax, Semantics, and Ambiguity

      • Alan P. Parkes
      Pages 37-47

    4. Regular Languages and Finite State Recognisers

      • Alan P. Parkes
      Pages 49-79

    5. Context Free Languages and Pushdown Recognisers

      • Alan P. Parkes
      Pages 81-106

    6. Important Features of Regular and Context Free Languages

      • Alan P. Parkes
      Pages 107-131

    7. Phrase Structure Languages and Turing Machines

      • Alan P. Parkes
      Pages 133-159

  4. Machines and Computation

    1. Front Matter

      Pages 161-161
      Download chapter PDF

    2. Finite State Transducers

      • Alan P. Parkes
      Pages 163-178

    3. Turing Machines as Computers

      • Alan P. Parkes
      Pages 179-201

    4. Turing’s Thesis and the Universality of the Turing Machine

      • Alan P. Parkes
      Pages 203-229

    5. Computability, Solvability, and the Halting Problem

      • Alan P. Parkes
      Pages 231-248

    6. Dimensions of Computation

      • Alan P. Parkes
      Pages 249-272

  5. Computation and Logic

    1. Front Matter

      Pages 273-273
      Download chapter PDF

    2. Boolean Logic and Propositional Logic

      • Alan P. Parkes
      Pages 275-290

    3. First Order Predicate Logic

      • Alan P. Parkes
      Pages 291-306

    4. Logic and Computation

      • Alan P. Parkes
      Pages 307-326

  6. Back Matter

    Pages 327-351
    Download chapter PDF
Back to top

Keywords

About this book

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).

Reviews

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)

Authors and Affiliations

  • Distributed Multimedia Research Group, Computing Department, Lancaster University, Lancaster

    Alan P. Parkes

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation