CS-501 Theory of Computation - Dec 2024 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. 8 Marks
   aWhat is a DFA machine? Design a deterministic finite automata machine over the alphabet set $\{0, 1\}$, accepting all strings starting and ending with different alphabet.
   How to answer

   • Define DFA as 5-tuple with transition function
   • Design logic for start and end symbols different
   • Draw transition diagram and transition table
   • Argue correctness of acceptance
2. 6 Marks
   bDefine finite-automata machine mathematically and explain its types.
   How to answer

   • Give 5-tuple mathematical definition Q, Sigma, delta, q0, F
   • Explain each component
   • Explain types: DFA, NFA, epsilon-NFA, Moore, Mealy
3. 6 Marks
   aConsider the following grammar for list structures: $S \to a / \wedge / (T)$ $T \to T,S / S$ Find left most derivation, right most derivation and parse tree for the string $(((a,a),\wedge(a)),a)$.
   How to answer

   • Apply productions S -> a/^/(T) and T -> T,S/S
   • Show leftmost derivation steps for (((a,a),^(a)),a)
   • Show rightmost derivation steps
   • Draw parse tree
4. 8 Marks
   bWrite the differences between Mealy and Moore machine. Convert the given Moore machine into its equivalent Mealy machine.

   

   How to answer

   • List differences: output timing, states vs transitions, etc.
   • Note Moore output per state q0/0,q1/0,q2/1
   • Construct Mealy transitions with output on edges
   • Draw equivalent Mealy machine
5. 8 Marks
   aDiscuss about the Chomsky hierarchy of languages with their grammar constraints rules and corresponding automata for each class.
   How to answer

   • State 4 Chomsky types 0-3
   • Give grammar constraints for each
   • Give corresponding automata: TM, LBA, PDA, FA
   • Give example languages
6. 6 Marks
   bDefine the regular expression. Find the regular expression for the given DFA machine.

   

   How to answer

   • Define regular expression
   • Apply state elimination / Arden's theorem to given DFA
   • Derive expression for paths to final q3
   • Simplify final regular expression
7. 8 Marks
   aFind a reduced Grammar equivalent to Grammar $G$, having Production rules $P$. $P: \{ S \to AC / B, A \to a, C \to c / BC, E \to aA / e \}$
   How to answer

   • Eliminate non-generating and non-reachable symbols
   • Remove epsilon/null productions for E -> e
   • Remove unit production S -> B
   • Give final reduced productions
8. 6 Marks
   bConstruct the PDA accepting the language $\{(ab)^n : n \ge 1\}$ by empty stack.
   How to answer

   • Define PDA tuple and empty-stack acceptance
   • Push (ab)^n pattern logic using stack
   • Give transition functions for push/pop
   • Show acceptance by empty stack
9. 8 Marks
   aMinimize the DFA using Myhill-Nerode Theorem.

   

   How to answer

   • Apply Myhill-Nerode distinguishability / partition method
   • Iteratively split states Q0-Q5
   • Merge equivalent states
   • Draw minimized DFA
10. 6 Marks
    bConvert the grammar $S \to AB, A \to BS / b, B \to SA / a$ into Greibach normal form.
    How to answer

    • Remove unit/epsilon productions if any
    • Order variables S,A,B
    • Substitute to get terminal-starting form
    • Introduce new variables to get A -> a alpha form
11. 6 Marks
    aExplain the different models of the Turing machines.
    How to answer

    • Define Turing machine model
    • Describe single-tape, multi-tape, NDTM, universal variants
    • Compare power and equivalence
    • Give schematic diagrams
12. 8 Marks
    bShow that $L = \{a^n b^n c^n / n \ge 1\}$ is not a context-free language.
    How to answer

    • State pumping lemma for CFL
    • Assume L = {a^n b^n c^n} is CFL
    • Choose pumping string and decomposition uvwxy
    • Derive contradiction, hence not CFL
13. 7 Marks
    aExplain the difference between tractable and intractable problems with examples.
    How to answer

    • Define tractable (P, polynomial) vs intractable (exponential/NP-hard)
    • Give examples: sorting vs TSP
    • Discuss decidability/complexity relevance
    • Conclude with table
14. 7 Marks
    bIs NPDA (non-deterministic PDA) and DPDA (deterministic PDA) equivalent or not? Illustrate with an example.
    How to answer

    • Define NPDA and DPDA acceptance power
    • State non-equivalence for CFL vs DCFL
    • Give example e.g. palindromes or {a^n b^n} vs {ww^R}
    • Conclude NPDA strictly more powerful
15. 4 Marks
    aExplain P and NP problems with examples.
    How to answer

    • Define P: polynomial-time solvable
    • Define NP: nondeterministic polynomial verifiable
    • Give examples for each
    • Mention P vs NP question
16. 10 Marks
    bWrite a short notes on the following:

    1. i)Universal Turing machine
    2. ii)Post Correspondence Problem
    How to answer

    • Define Universal Turing Machine simulation
    • Explain encoding and halting aspect
    • Define PCP statement and undecidability
    • Give example instance of PCP