Introduction to Computer TheoryThis text strikes a good balance between rigor and an intuitive approach to computer theory. Covers all the topics needed by computer scientists with a sometimes humorous approach that reviewers found "refreshing." The goal of the book is to provide a firm understanding of the principles and the big picture of where computer theory fits into the field. |
Contents
Languages | 2 |
Recursive Definitions | 21 |
Regular Expressions | 31 |
Copyright | |
25 other sections not shown
Other editions - View all
Common terms and phrases
2PDA a-edge A-productions a's and b's aaabbb abaaba accepts the language alphabet begin branch cell Chapter character circuit concatenation constructive algorithm context-free languages convert crash CYK algorithm definition DELETE derivation tree edge labeled exactly EXAMPLE Let FA₂ final finite grammar guage HALT infinite input letters input string L₁ L₂ language accepted language defined leftmost derivation loop mathematical Mealy machine means Moore machine move the TAPE Myhill-Nerode theorem Net(READ non-context-free nondeterministic nonregular nonterminal number of a's output PALINDROME path possible problem PROD proof prove pumping lemma PUSH pushdown transducer read a b READ₂ recursive regular expression regular languages REJECT replace row language Rule self-embedded sequence simulation STACK Step string of terminals strings of a's substring symbol TAPE HEAD theorem Turing machine word X₁ y₁ y₂