1. What is the significance of closure properties in automata theory?
2. How does the power of DFA change if multiple start states are allowed?
3. How does adding ε-transitions to an NFA affect its computational power?
4. Can every NFA be minimized? Explain.
5. How is the transition diagram of a DFA different from that of an NFA?
6. How do you prove that a given language is not regular using the pumping lemma?
7. How do regular languages handle infinite input strings?
8. What is the decision problem for regular languages?
9. How does the Myhill-Nerode Theorem help in proving language regularity?
10. What is the role of regular expressions in automata theory?
11. How does the equivalence of DFA and NFA work?
12. What is the process of converting an NFA with ε-moves to a DFA?
13. How do regular languages relate to finite automata and regular expressions?
14. How does the Kleene star operator affect the expressiveness of regular expressions?
15. How do you minimize a DFA?
16. How does the Chomsky hierarchy classify languages based on their automaton models?
17. What is the difference between left-linear and right-linear grammars?
18. How do you prove that a context-free language is not regular?
19. How do you convert a context-free grammar to Chomsky Normal Form (CNF)?
20. How does the CYK algorithm parse a context-free grammar?
21. What is the difference between weak and strong equivalence in grammars?
22. How does a Pushdown Automaton (PDA) work with context-free languages?
23. How does nondeterminism affect the computational power of a PDA?
24. Can all context-free languages be accepted by deterministic PDA? Explain.
25. What is the relationship between context-free languages and deterministic PDAs?
26. How does ambiguity in context-free grammars affect parsing?
27. How do you resolve ambiguity in context-free grammars?
28. What are the closure properties of context-free languages?
29. How do you prove that a language is context-free using the pumping lemma for CFLs?
30. What is the importance of Greibach Normal Form in context-free grammars?
31. How does context-free grammar handle recursive language structures?
32. How is a Pushdown Automaton (PDA) different from a finite automaton?
33. What is the significance of two-stack PDA in relation to Turing machines?
34. How do Linear Bounded Automata (LBA) relate to context-sensitive languages?
35. What is the computational power of LBAs compared to Turing machines?
36. How do Turing machines recognize context-sensitive languages?
37. What is the role of auxiliary space in space-bounded computations?
38. How do you prove that a language is context-sensitive?
39. What is the relationship between Linear Bounded Automata (LBA) and PSPACE?
40. How does the closure of context-sensitive languages under intersection differ from CFLs?