Theory of Computation (TOC) - Viva Questions
1. What is Theory of Computation? Explain its importance.
2. Define the terms alphabet, string, and language in the context of formal languages.
3. What is a finite automaton? Explain its components.
4. Differentiate between DFA and NFA with examples.
5. What are regular expressions? How are they related to finite automata?
6. Explain the concept of epsilon transitions in NFA. How can they be removed?
7. What is the difference between a Moore machine and a Mealy machine?
8. Define the Chomsky hierarchy. Explain the types of grammars.
9. What are context-free languages? Provide examples.
10. How is a pushdown automaton (PDA) different from a finite automaton?
11. What are the components of a Turing Machine?
12. Define and differentiate between decidable and undecidable problems.
13. What is the halting problem? Why is it undecidable?
14. Explain the concept of a universal Turing machine.
15. What are recursive and recursively enumerable languages?
16. What are the applications of finite automata in real-world scenarios?
17. Explain the pumping lemma for regular languages. Provide an example.
18. What is a context-sensitive language? How is it different from context-free languages?
19. Define the concept of reduction in computability theory.
20. Explain the difference between P, NP, NP-complete, and NP-hard problems.
