Theory of Computation MCQ for Bihar STET with Answers, PYQs & Notes

Tests in this unit

• Mock TestThe 30-question Unit 11 mock paper from the notes, in book order.30 Q
• PYQ OnlyQuestions asked in the 2023 and 2025 STET papers, with corrected keys.31 Q
• Practice BankTopic-wise questions: DFA/NFA, regular expressions, CFGs, PDAs, Turing machines and undecidability.52 Q
• Full TestPYQs and the practice bank together.83 Q
• Quick Test30 questions picked at random.30 Q

Unit 11 syllabus: Theory of Computation

1. Introduction; alphabets, strings and languages; automata and grammars; deterministic finite automata (DFA): formal definition, simplified notation, state transition graph, transition table, language of DFA; non-deterministic finite automata (NFA), NFA with epsilon transition, language of NFA; equivalence of NFA and DFA; minimization of finite automata; distinguishing one string from other.
2. Regular expression (RE): definition, operators and their precedence, algebraic laws; Kleene's theorem; RE to FA, DFA to RE; Arden's theorem; non-regular languages; pumping lemma for regular languages and its application; closure and decision properties of regular languages; FA with output: Moore and Mealy machines and their equivalence; applications and limitations of FA.
3. Context free grammar (CFG) and context free languages (CFL): definition, examples, derivation, derivation trees, ambiguity in grammar, inherent ambiguity, ambiguous to unambiguous CFG, useless symbols, simplification of CFGs; normal forms: CNF and GNF; closure properties of CFLs; decision properties: emptiness, finiteness and membership; pumping lemma for CFLs.
4. Push down automata (PDA): description and definition, instantaneous description, language of PDA, acceptance by final state and by empty stack, deterministic PDA, equivalence of PDA and CFG, CFG to PDA and PDA to CFG, two stack PDA.
5. Turing machines (TM): basic model, definition and representation, instantaneous description, language acceptance by TM, variants of TM, TM as computer of integer functions, universal TM, Church's thesis, recursive and recursively enumerable languages, halting problem, introduction to undecidability, undecidable problems about TMs, Post correspondence problem (PCP), modified PCP, introduction to recursive function theory.