# AUTOMATA AND COMPUTABILITY

Language: English

Pages: 413

ISBN: 0387949070

Format: PDF / Kindle (mobi) / ePub

This textbook provides undergraduate students with an introduction to the basic theoretical models of computability, and develops some of the model's rich and varied structure. The first part of the book is devoted to finite automata and their properties. Pushdown automata provide a broader class of models and enable the analysis of context-free languages. In the remaining chapters, Turing machines are introduced and the book culminates in analyses of effective computability, decidability, and Gödel's incompleteness theorems. Students who already have some experience with elementary discrete mathematics will find this a well-paced first course, and a number of supplementary chapters introduce more advanced concepts.

UNDERGRADUATE TEXTS IN COMPUTER SCIENCE Editors David Gries Fred B. Schneider UNDERGRADUATE TEXTS IN COMPUTER SCIENCE Beidler, Data Structures and Algorithms Bergin, Data Structure Programming Brooks, C Programming: The Essentials for Engineers and Scientists Brooks, Problem Solving with Fortran 90 Dandamudi, Introduction to Assembly Language Programming Gril/meyer, Exploring Computer Science with Scheme Jalote, An Integrated Approach to Software Engineering, Second Edition Kizza, Ethical and

between M and N, in which case the algorithm halts and reports failure. For the case M = N, the algorithm computes the maximal autobisimulation. The algorithm is a direct generalization of the algorithm of Lecture 14. As in Lecture 14, the algorithm will mark pairs of states (p, q), where p E QM and q E QN. A pair (p,q) will be marked when a proof is discovered that p and q cannot be related by any bisimulation. 1. Write down a table of all pairs (p,q), initially unmarked. 2. Mark (p,q) if p E

called the carrier of A, along with a map that assigns a function IA or relation RA of the appropriate arity to each function symbol leE or relation symbol R e E. If I is an n-ary function symbol, then the function associated with I must be an n-ary function IA : An -+ A. If R is an n-ary relation symbol, then the relation RA must be an n-ary relation RA ~ An. Constant function symbols c are interpreted as O-ary functions (functions with no inputs), which are just elements cA of A. A unary

The Myhill-Nerode Theorem for Term Automata 117 Let ~ be a signature consisting of finitely many function symbols and a single unary relation symbol R. For a given A ~ TE and ground terms s, tETE, define s ==A t ~ for all contexts u, s:(u) E A {=:} st(u) E A. It is not difficult to argue that ==A is a congruence on TE(A) (Miscellaneous Exercise 68). Theorem D.3 (Myhill-Nero de theorem for term automata) Let A ~ TE • Let TE(A) denote the term algebra over ~ in which R is interpreted as the

` := `

`I` I «arith-expr> ::= + I - I * I / ::= 0 11 I 2 I 3 I 4 I 5 I 6 I 7 I 8 I 9

`::= a I b I c I ... I x I y`