1. What is the definition of "Theory of Computation"?
2. What are the three main branches of the Theory of Computation?
3. What is a finite automaton?
4. What is the difference between deterministic and non-deterministic finite automata (DFA and NFA)?
5. Define regular languages.
6. What are regular expressions?
7. How does a finite automaton recognize a language?
8. What is a transition function in DFA?
9. Can DFA and NFA recognize the same class of languages?
10. What is a language in the context of automata theory?
11. How is a DFA formally defined?
12. What is the significance of an accepting state in DFA?
13. What are ε-transitions in NFA?
14. What is the pumping lemma for regular languages?
15. How can you prove that a language is not regular using the pumping lemma?
16. What are context-free grammars (CFG)?
17. How are CFGs different from regular languages?
18. What is a pushdown automaton (PDA)?
19. What is the difference between deterministic and non-deterministic pushdown automata (DPDA and NPDA)?
20. What is the Chomsky hierarchy?
21. Where do regular languages fall in the Chomsky hierarchy?
22. Define context-free languages.
23. How does a PDA recognize context-free languages?
24. What is a Turing machine?
25. How is a Turing machine different from a finite automaton?
26. What is the Church-Turing thesis?
27. What does it mean for a problem to be "decidable"?
28. What is an undecidable problem?
29. Can a DFA simulate a Turing machine?
30. What is a universal Turing machine?
31. What are recursively enumerable languages?
32. How are recursively enumerable languages different from recursive languages?
33. What is the halting problem?
34. What is meant by the term "computability"?
35. What is the relationship between decidability and computability?
36. What is the importance of the Turing machine model in TOC?
37. What is a multi-tape Turing machine?
38. Can multi-tape Turing machines recognize more languages than single-tape Turing machines?
39. What is a linear bounded automaton (LBA)?
40. What languages are recognized by LBAs?