CS-501 Theory of Computation - Dec 2025 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aExplain finite automata as language acceptors and translators.
   How to answer

   • Define finite automata as 5-tuple
   • Explain language acceptor mode with acceptance by final state
   • Explain translator/transducer mode - Mealy and Moore concept
   • Give example of each
2. 7 Marks
   bDesign a Mealy machine that outputs 1 whenever the input symbol is '1', otherwise outputs 0.
   How to answer

   • Define Mealy machine output on transition
   • Design states to remember last input
   • Give transition table with output 1 on input '1' else 0
   • Draw state transition diagram
3. 7 Marks
   aExplain deterministic and non-deterministic finite automata with examples.
   How to answer

   • Define DFA with single next state function
   • Define NFA/NDFA with set of next states
   • Compare transition function and determinism
   • Give example DFA and NFA diagrams
4. 7 Marks
   bConvert the given NDFA to an equivalent DFA: States $\{q0, q1\}$, Alphabet $\{a, b\}$, Transitions: $\delta(q0, a)=\{q0, q1\}$, $\delta(q0, b)=\{q0\}$, $\delta(q1, b) = \{q1\}$. Final state= q1.
   How to answer

   • List NFA states, alphabet and transitions
   • Apply subset construction to get DFA states
   • Construct DFA transition table
   • Identify final states containing q1 and draw DFA
5. 7 Marks
   aExplain regular expressions and Arden's theorem.
   How to answer

   • Define regular expression operators
   • State Arden's theorem $R = Q + RP$ implies $R = QP^*$
   • Give assumptions and proof outline
   • Give example application to solve equations
6. 7 Marks
   bWrite a regular expression for the language over $\{a, b\}$ that contains strings ending with "ab".
   How to answer

   • Define alphabet {a,b}
   • Explain pattern for strings ending in 'ab'
   • Write expression $(a+b)^*ab$
   • Justify correctness
7. 7 Marks
   aExplain context free grammar and derivation trees.
   How to answer

   • Define CFG 4-tuple (V,T,P,S)
   • Explain derivation - leftmost/rightmost
   • Define derivation/parse tree
   • Give example
8. 7 Marks
   bFor the grammar: $S \to aSb \mid ab$, derive the string "aabb" and draw its parse tree.
   How to answer

   • Start from S and apply S -> aSb
   • Apply S -> ab to get aabb
   • Show leftmost derivation steps
   • Draw parse tree with root S
9. 7 Marks
   aExplain ambiguity in grammar and methods to remove it.
   How to answer

   • Define ambiguous grammar with two parse trees
   • Give example
   • Explain methods: precedence, associativity, rewriting
   • Explain removal to get unambiguous grammar
10. 7 Marks
    bConvert the grammar into Chomsky Normal Form: $S \to AB \mid a, A \to a, B \to b$.
    How to answer

    • Check given productions for CNF form
    • Replace terminals and break long productions
    • Introduce new variables if needed
    • List final CNF productions
11. 7 Marks
    aExplain pushdown automata and deterministic and non-deterministic PDAs.
    How to answer

    • Define PDA 7-tuple with stack
    • Explain deterministic PDA single move
    • Explain non-deterministic PDA multiple moves
    • Compare power with example
12. 7 Marks
    bDesign a PDA for the language $L=\{a^n b^n \mid n \ge 1\}$.
    How to answer

    • Define language $L={a^n b^n | n \ge 1}$
    • Design stack operation push a's pop on b's
    • Define states and transitions
    • Draw PDA transition diagram and test
13. 7 Marks
    aExplain Turing machines and techniques for their construction.
    How to answer

    • Define Turing machine 7-tuple
    • Explain tape, head and transitions
    • Explain construction techniques - storage, subroutines, multitape
    • Give example
14. 7 Marks
    bDesign a Turing machine to accept strings over $\{0,1\}$ having even number of 1's.
    How to answer

    • Define requirement even number of 1's
    • Design two states for even/odd parity
    • Define transitions on 0,1 and blank
    • Draw TM diagram and show acceptance
15. 7 Marks
    aExplain decidable, undecidable, recursive, and recursively enumerable languages.
    How to answer

    • Define decidable/recursive languages
    • Define undecidable and recursively enumerable
    • Relate to Turing machine halting/acceptance
    • Give examples of each class
16. 7 Marks
    bWhat is the halting problem? Explain why it is undecidable.
    How to answer

    • Define halting problem statement
    • Explain diagonalization / proof by contradiction
    • Show no TM can decide halting
    • Conclude undecidability implications