CS-501 Theory of Computation - Jun 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 Moore and Mealy machines with examples. How do they differ in output behaviour?
   How to answer

   • Define Moore machine: output associated with states
   • Define Mealy machine: output associated with transitions
   • Give example of each with state table/diagram
   • Compare output behaviour: timing, length, number of outputs
2. 7 Marks
   bConvert the given Moore machine to a Mealy machine: States: $\{A, B\}$ Output: $A/0, B/1$ Transitions: $A \to aB, A \to bA, B \to aA, B \to bB$
   How to answer

   • Recall Moore outputs: A/0, B/1
   • Apply rule: Mealy output on transition = output of destination Moore state
   • List Mealy transitions with outputs
   • Draw resulting Mealy transition table/diagram
3. 7 Marks
   aWhat is a 2-way DFA? How does it differ from standard DFA in terms of tape head movement?
   How to answer

   • Define 2-way DFA with ability to move head left/right/stationary
   • Describe tape with end-markers
   • Contrast with standard 1-way DFA head moves only left to right
   • Note equivalence in language power
4. 7 Marks
   bMinimize the DFA with states $\{A,B,C,D\}$, where $A$ is initial, $C$ is final, and transitions: $A \to aB, A \to bA; B \to aC, B \to bA; C \to aC, C \to bD; D \to aC, D \to bA$
   How to answer

   • List initial state A and final state C
   • Apply partition refinement / Myhill-Nerode for 0,1-equivalence
   • Identify equivalent states e.g. A and D or B etc.
   • Construct minimized DFA transition table
5. 7 Marks
   aExplain ambiguity in context-free grammars with an example. How can it be resolved?
   How to answer

   • Define ambiguous grammar: two parse trees/leftmost derivations
   • Give classic example e.g. E->E+E|E*E|id
   • Show two parse trees for same string
   • Explain resolution: precedence, associativity, unambiguous rewrite
6. 7 Marks
   bConvert the grammar $S \to aSb \mid SS \mid \varepsilon$ to Chomsky Normal Form (CNF).
   How to answer

   • Eliminate epsilon and unit productions
   • Introduce new variables for terminals a,b
   • Break long production aSb into binary form
   • List final CNF productions
7. 7 Marks
   aDescribe the conversion from PDA to CFG using the standard algorithm.
   How to answer

   • State equivalence of PDA and CFG
   • Describe triple construction [p,A,q] variables
   • Give productions for push, pop and state change
   • Mention start symbol and correctness idea
8. 7 Marks
   bConstruct a PDA for the language $L = \{ww^R \mid w \in (a+b)\}$
   How to answer

   • Define language of even palindromes over {a,b}
   • Push input symbols nondeterministically guessing middle
   • Switch to popping and matching reverse
   • Accept on empty stack
9. 7 Marks
   aCompare multi-tape and multi-head Turing machines. How do they affect computational power?
   How to answer

   • Define multi-tape vs multi-head single tape models
   • Compare structure: tapes vs heads
   • Discuss simulation and time complexity difference
   • Conclude same computational power as single-tape TM
10. 7 Marks
    bExplain the concept of NP-complete problems with examples.
    How to answer

    • Define NP and polynomial-time reduction
    • Define NP-complete: in NP and NP-hard
    • Give examples: SAT, 3-SAT, Hamiltonian, TSP
    • Mention Cook-Levin theorem
11. 14 Marks
    Differentiate between decidable and recursively enumerable languages.
    How to answer

    • Define decidable: TM halts with accept/reject
    • Define recursively enumerable: TM accepts, may loop otherwise
    • Compare closure and existence of recognizer vs decider
    • Give example: Halting language is RE but undecidable
12. 7 Marks
    aDiscuss the significance of the Recursion Theorem in computability theory.
    How to answer

    • State Recursion Theorem / fixed-point statement
    • Explain self-reference and quines
    • Discuss applications in undecidability proofs
    • Note significance for computability theory
13. 7 Marks
    bProve that the Halting Problem is undecidable using diagonalization.
    How to answer

    • Assume halting decider H exists
    • Construct diagonal machine D that does opposite
    • Derive contradiction on D(D)
    • Conclude Halting Problem undecidable
14. 14 Marks
    For the regular expression $(a+b)ab(a+b)$, calculate the minimum number of states in equivalent NFA and DFA.
    How to answer

    • Interpret regex as strings with ab in middle positions
    • Construct NFA using Thompson construction and count states
    • Convert to DFA via subset construction and minimize
    • State minimum NFA vs DFA state counts