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. |
Other editions - View all
Common terms and phrases
accepted algebraic alphabet arithmetic operations automaton basic binary operation bit operations Chinese Remainder Theorem Church-Turing Thesis composite computer science congruence context-free grammars context-free languages context-sensitive context-sensitive languages cryptosystem decidable decision problem Decryption defined Definition denoted deterministic digits Diophantine equation discrete logarithms divisor element elliptic curve Encryption equivalent Euclid's algorithm Example exponential EXPTIME Fermat finite automata finite set graph Horn clause input integer factorization L₁ log log m₁ mathematician mathematics method mod nk mod q modulo multiplication n₁ nondeterministic NP-complete number theory number-theoretic functions P₁ P₂ polynomial positive integer primality testing prime factor Prime Number primitive recursive probabilistic Turing machine proof proposition prove pseudoprimality public-key push-down automata quadratic quantum random number real numbers recursive functions recursively enumerable languages regular languages residue sequence simple continued fraction solve string subsection Suppose tape undecidable vertex Z/nZ