𝔖 Scriptorium
✦   LIBER   ✦

πŸ“

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

✍ Scribed by Alan P. Parkes BSc, PhD (auth.)


Publisher
Springer-Verlag London
Year
2002
Tongue
English
Leaves
351
Edition
1
Category
Library

⬇  Acquire This Volume

No coin nor oath required. For personal study only.

✦ Synopsis


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

✦ Table of Contents


Front Matter....Pages i-xi
Introduction....Pages 1-7
Front Matter....Pages 9-9
Elements of Formal Languages....Pages 11-36
Syntax, Semantics, and Ambiguity....Pages 37-47
Regular Languages and Finite State Recognisers....Pages 49-79
Context Free Languages and Pushdown Recognisers....Pages 81-106
Important Features of Regular and Context Free Languages....Pages 107-131
Phrase Structure Languages and Turing Machines....Pages 133-159
Front Matter....Pages 161-161
Finite State Transducers....Pages 163-178
Turing Machines as Computers....Pages 179-201
Turing’s Thesis and the Universality of the Turing Machine....Pages 203-229
Computability, Solvability, and the Halting Problem....Pages 231-248
Dimensions of Computation....Pages 249-272
Front Matter....Pages 273-273
Boolean Logic and Propositional Logic....Pages 275-290
First Order Predicate Logic....Pages 291-306
Logic and Computation....Pages 307-326
Back Matter....Pages 327-351

✦ Subjects


Mathematical Logic and Formal Languages; Computation by Abstract Devices; Theory of Computation; Computational Mathematics and Numerical Analysis


πŸ“œ SIMILAR VOLUMES


Introduction to Languages, Machines, and
✍ Alan P. Parkes πŸ“‚ Library πŸ“… 2002 πŸ› Springer 🌐 English

A well-written and accessible introduction to the most important features of formal languages and automata theory. It focuses on the key concepts, illustrating potentially intimidating material through diagrams and pictorial representations, and this edition includes new and expanded coverage of top

An introduction to formal languages and
✍ Song Y. Yan. πŸ“‚ Library πŸ“… 1998. πŸ› World Scientific 🌐 English

This book provides an elementary introduction to formal languages and machine computation. The materials covered include computation-oriented mathematics, finite automata and regular languages, push-down automata and context-free languages, Turing machines and recursively enumerable languages, and c

An Introduction to Formal Languages and
✍ Yan S.Y. πŸ“‚ Library πŸ“… 1996 πŸ› World Scientific 🌐 English

This book provides an elementary introduction to formal languages and machine computation. The materials covered include computation-oriented mathematics, finite automata and regular languages, push-down automata and context-free languages, Turing machines and recursively enumerable languages, and c