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. |
Contents
| 1 | |
Chapter 2 Formal Languages and Automata | 95 |
Chapter 3 Turing Computability and Complexity | 163 |
Chapter 4 NumberTheoretic Computations and Applications | 245 |
Other editions - View all
Common terms and phrases
accepted algebraic Alice alphabet arithmetic operations automaton base biological computation bit operations called CFRAC Chinese Remainder Theorem 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 Encryption Euclid's algorithm Example exponential EXPTIME Fermat finite automata finite set goto graph Horn clause input integer factorization Lucas mathematician Mathematics Mersenne prime method mod n2 mod q models modulo multiplication nondeterministic number theory O(log polynomial positive integer primality testing prime factor prime number primitive recursive probabilistic Turing machine probable prime proof proposition prove pseudoprimality public-key push-down automata quadratic quantum computer random number real numbers recursive functions recursively enumerable languages regular languages residue sequence simple continued fraction solution solve string subsection Suppose symbol tape undecidable Z/nZ