## Elementary Computability, Formal Languages, and AutomataEmphasizes the theory of computability & the theory of formal languages. Uses automata as precise models of computation in studies that have actual computers as their primary application. |

### What people are saying - Write a review

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

### Contents

TURING MACHINES | 23 |

COMPUTABLE FUNCTIONS | 84 |

GODEL NUMBERING AND CHURCHS | 148 |

Copyright | |

10 other sections not shown

### Common terms and phrases

alphabet ambiguous arguments assume asterisk beginning Chapter character Church's thesis command computable functions construction context-free grammar cycle decision procedure defined denotes derivation tree deterministic parsing divisor DO-TIMES program edge Euclidean algorithm example execution Exercise explicit definition flowchart formal languages foundational programming languages function symbol functional expression G-PRE given Godel number GOTO language halting problem induction input head input string input tape labeled lambda productions Lemma loop mated mathematical mathematical induction mu-recursive mu-recursive functions nondeterministic nonnegative integers nonnull strings nonterminal Note number of c's occur operator output parentheses parsing automaton parsing tape positive integers prime primitive recursion primitive-recursive functions proof propositional calculus prove regular expression regular languages right side rightmost Section semantics semi-Thue system semigroup sequence set of strings square step storage position substring syntactic category terminal Theorem theory of computability tion total configuration total function transition graph Turing machine unambiguous variables write zero