AD-501 Theory of Computation - Nov 2023 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
   aProve that $1^2 + 2^2 + 3^3 + ...\ n^2 = \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ using mathematical induction.
   How to answer

   • State principle of mathematical induction: base case and inductive step.
   • Verify base case for n=1.
   • Assume true for n=k and prove for n=k+1 using algebra.
   • Conclude formula holds for all n.
2. 7 Marks
   bExplain the purpose of Mealy machine and Moore machine. Write application area of Mealy and Moore machine. Convert the following Mealy machine into Moore Machine.

   

   How to answer

   • Define Mealy and Moore machines and difference in output association.
   • Explain purpose: Mealy as translator, Moore as acceptor/generator.
   • List application areas for both.
   • Apply Mealy to Moore conversion procedure to get equivalent Moore machine.
3. 7 Marks
   aConvert epsilon-NFA to NFA. Consider the example having states q0, q1, q2, q3 and q4.

   

   How to answer

   • Define epsilon-closure for each state.
   • Compute epsilon-NFA transition table.
   • Derive equivalent NFA transitions without epsilon.
   • Identify start and final states of resulting NFA.
4. 7 Marks
   bConstruct a regular expression corresponding to the automata using Arden's theorem. Write the applications of Arden's Theorem.

   

   How to answer

   • Write state equations for the given automata.
   • State Arden's theorem and condition for application.
   • Solve equations by substitution to get regular expression.
   • List applications of Arden's theorem.
5. 7 Marks
   aWhat do you mean by Parsing? How left most and right most derivation helps to find out the ambiguity in a grammar?
   How to answer

   • Define parsing in context of CFG.
   • Define leftmost and rightmost derivations.
   • Explain how two different parse trees show ambiguity.
   • Give example of ambiguous grammar.
6. 7 Marks
   bObtain DFAs to accept strings of $a$'s and $b$'s having exactly one $a$.
   How to answer

   • Define language with exactly one a over {a,b}.
   • Design states for zero, one and more than one a.
   • Draw DFA transition diagram.
   • Mention final state and trap state.
7. 7 Marks
   aExplain the Patri nets model with example.
   How to answer

   • Define Petri nets: places, transitions, tokens.
   • Explain firing rules and marking.
   • Draw example net diagram.
   • Give application example.
8. 7 Marks
   bDesign a push down automata for language $L=\{a^n b^n|n>=1\}$. Also check the acceptability of string "aaaabbab".
   How to answer

   • Define PDA for L = {a^n b^n | n>=1}.
   • Describe stack operations for a's and b's.
   • Draw transition diagram of PDA.
   • Trace string aaaabbab to show rejection.
9. 7 Marks
   aExplain the terms P, NP, NP complete. Give suitable example. https://www.rgpvonline.com
   How to answer

   • Define classes P, NP and NP-complete.
   • Explain polynomial time and nondeterminism.
   • Give suitable examples for each class.
   • Mention relation and significance.
10. 7 Marks
    bDesign a Turing machine that computes 2's complement of given string over the $\Sigma = \{0, 1\}$. Show the output of your machine for string "00000".
    How to answer

    • Describe Turing machine logic for 2's complement.
    • Define states and tape transitions over Sigma={0,1}.
    • Draw state diagram of machine.
    • Show computation/output for input 00000.
11. 7 Marks
    aExplain the types of Automata and prove that the Finite Automata as a language acceptor and translator.
    How to answer

    • List types of automata: FA, PDA, TM etc.
    • Define language acceptor vs translator.
    • Prove FA can accept language and translate with output.
    • Give examples of acceptor and Mealy/Moore translator.
12. 7 Marks
    bExplain Greibach and Chomsky Normal Form.
    How to answer

    • Define Chomsky Normal Form with A->BC, A->a rules.
    • Define Greibach Normal Form with A->aAlpha rules.
    • Explain conversion steps for each.
    • Give examples.
13. 7 Marks
    aApply minimization of the following DFA using Equivalence theorem.

    

    How to answer

    • Construct transition table for given DFA with states q0-q4.
    • Apply partition into equivalence classes iteratively.
    • Merge equivalent states.
    • Draw minimized DFA.
14. 7 Marks
    bWrite given CFG for R.E $(011 + 1)^*(01)^*$.
    How to answer

    • Recall regular expression $(011+1)^*(01)^*$.
    • Introduce variables for sub-expressions.
    • Write productions generating the language.
    • Present final CFG.
15. 14 Marks
    Write the short notes on following : (any two)

    1. a)Variation of Turing Machine
    2. b)Two way finite automata
    3. c)Multitape
    4. d)Halting problem of Turing machine
    How to answer

    • Select any two topics from given list.
    • Define each with key features/diagram.
    • Give example or significance.
    • Conclude with applications.