Introduction to Computer TheoryA fundamentally sound exploration of computer theory, it has at its core one compound goal--to define a computer and then explain the definition. The author builds mathematical skills while presenting the subject matter. The text is divided into three parts covering automata theory, pushdown automata theory, and Turing theory. Additionally, two new theorems are explored, including the regular language division theorem and the Rabin-Shephardson Theorem. Also introduced in this printing are transition Turing machines. A table of theorems and index complete this work. |
Common terms and phrases
a's and b's accepted algorithm allow alphabet apply becomes begin branch build called cell Chapter character concatenation consider constructive contains context-free convert corresponding crash defined definition derivation double edge equivalent exactly example FA's factor final finite give given grammar HALT infinite input string instruction labeled language lead leave length letter looks loop machine means method move never nonterminals Notice number of a's once operation output path picture possible problem PROD productions proof prove PUSH question recursive regular expression REJECT replace Rule sequence simulate STACK start starting Step STORE substring symbol TAPE HEAD terminals Theorem transition tree Turing word write