## An Introduction to Formal Languages and Machine ComputationThis book provides a concise and modern introduction to Formal Languages and Machine Computation, a group of disparate topics in the theory of computation, which includes formal languages, automata theory, turing machines, computability, complexity, number-theoretic computation, public-key cryptography, and some new models of computation, such as quantum and biological computation. As the theory of computation is a subject based on mathematics, a thorough introduction to a number of relevant mathematical topics, including mathematical logic, set theory, graph theory, modern abstract algebra, and particularly number theory, is given in the first chapter of the book. The book can be used either as a textbook for an undergraduate course, for a first-year graduate course, or as a basic reference in the field. |

### What people are saying - Write a review

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

### Contents

ComputationRelated Mathematics | 1 |

Formal Languages and Automata | 95 |

Turing Computability and Complexity | 163 |

NumberTheoretic Computations and Applications | 245 |

New Models of Computation | 361 |

381 | |

393 | |

### Other editions - View all

### Common terms and phrases

accepted algebraic Alice alphabet arithmetic operations automaton base basic binary operation biological computation bit operations called CFRAC Chinese Remainder Theorem Church-Turing Thesis class of languages composite computer science congruence context-free grammars context-free languages context-sensitive cryptography cryptosystem decision problem Decryption defined Definition denoted deterministic digits Diophantine equation divisor element elliptic curve encrypted equivalent Euclid's algorithm Example exponential EXPTIME Fermat finite automata finite set gcd(a given goto graph Horn clause input integer factorization Lucas mathematician mathematics Mersenne prime method mod NB mod q mod TV modulo multiplication nondeterministic number theory polynomial positive integer primality testing prime factor prime number primitive recursive probabilistic Turing machine probable prime proof proposition prove public-key push-down automata quadratic random number real numbers recursive functions recursively enumerable languages regular languages residue sequence simple continued fraction solve string subsection Suppose symbol tape undecidable vertex Z/nZ