theory of computation
the idea behind digital computers may be explained by saying that these machines are intended to carry out any operations which could be done by a human computer. the human computer is supposed to be following fixed rules; he has no authority to deviate from them in any detail. we may suppose that these rules are supplied in a book, which is altered whenever he is put on to a new job. he has also an unlimited supply of paper on which he does his calculations. Alan Turing, 1950.
[cite:;taken from @computability_arora_2009 chapter 1]
[cite:;taken from @computability_arora_2009 chapter 1]
nodes
- theory of computation problems
- alphabet
- language
- deterministic finite automaton
- nondeterministic finite automaton
- regular expression
- regular language
- context-free grammar
- context-free language
- pumping lemma for regular languages
- pumping lemma for context free languages
books
(princ (book-collage (list "blk:1700074012" "blk:1700296770")))
.png)
Introduction to Automata Theory, Languages, and Computation
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
2006
.png)
Introduction to the Theory of Computation Third Edition
Michael Sipser
2012