Computer Science - Graduate CS - Theory of computation - Theory of Computation Quiz

8 questions. Q1: A DFA can recognize? → Regular languages (patterns describable by regex). Q2: The Halting Problem is? → Undecidable (no algorithm can solve it for all programs). Q3: Church-Turing thesis states? → Anything computable can be computed by a Turing Machine. Q4: Context-free grammars are