AD-501 Theory of Computation - Nov 2022 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. 14 Marks
   Construct a Mealy machine for binary language to determine the residue modulo 5.
   How to answer

   • Define states for residues 0-4 and input alphabet {0,1}
   • Give transition: next residue = (2*current + input) mod 5
   • Give output as next residue / residue value
   • Present transition table and state diagram of Mealy machine
2. 7 Marks
   aDesign a DFA accepting set of all strings containing exactly 2a's and exactly 2b's.
   How to answer

   • Define counting of a's (0,1,2,>2) and b's (0,1,2,>2)
   • Construct product DFA with 16 states including dead state
   • Mark state with exactly 2 a's and exactly 2 b's as final
   • Draw transition diagram
3. 7 Marks
   bDesign an NFA accepting strings containing neither aa nor bb.
   How to answer

   • Language is alternating a and b with no aa and no bb
   • Define states for last symbol seen and dead state
   • Add epsilon / nondeterministic choices if used
   • Draw NFA transition diagram and justify acceptance
4. 7 Marks
   aConvert the following Finite Automata to its equivalent Regular Expression.

   

   How to answer

   • Identify states $q_0$ (start), $q_1$, $q_2$ (final) and transitions shown
   • Apply state elimination / Arden's theorem step by step
   • Eliminate $q_1$ then $q_0$ to obtain expression for $q_2$
   • Write final equivalent regular expression
5. 7 Marks
   bCheck whether the given grammar is ambiguous. $S \to A1B$, $A \to 0A|\varepsilon$, $B \to 0B|1B|\varepsilon$ and construct leftmost and rightmost derivations for the string 00101.
   How to answer

   • Define ambiguous grammar and leftmost/rightmost derivations
   • Derive string $00101$ leftmost using $S \to A1B$ productions
   • Derive string $00101$ rightmost
   • Conclude ambiguous if two distinct parse trees/derivations exist
6. 7 Marks
   aConstruct a grammar in CNF for the given grammar $G = <V, T, P, S>$ where $V=\{S, A, B\}$, $T=\{0, 1\}$ and $P: \{S \to 0B|1A,\ A \to 0S|1AA|0,\ B \to 1S|0BB|1\}$, S.
   How to answer

   • Eliminate epsilon, unit and useless productions from given grammar
   • Introduce new variables for terminals 0,1
   • Break long productions into binary form
   • List final CNF productions
7. 7 Marks
   bConstruct the grammar in GNF for the given grammar $G: A_1 \to A_2A_3, A_2 \to A_3A_1|a, A_3 \to A_1A_2|b$.
   How to answer

   • Order variables $A_1,A_2,A_3$ and ensure increasing indices
   • Substitute $A_3$ and $A_2$ productions to remove left recursion
   • Ensure each production starts with terminal
   • List final GNF productions
8. 7 Marks
   aDesign a PDA for the language $L = \{x/x \in n_a(x) = n_b(x)$ and $x \in \{a, b\}^*\}$ by final state.
   How to answer

   • Define $n_a(x)=n_b(x)$ language over $\{a,b\}$
   • Use stack to count excess of a over b
   • Define states and transitions for push/pop on a/b
   • Accept by final state with empty / balanced condition
9. 7 Marks
   bConstruct CFG for the PDA given below $A=(\{q_0,q_1\}, \{0,1\}, \{S,A\}, \delta, q_0, S, \varphi)$ where $\delta$ is given as below $\delta(q_0, 1, S)=\{(q_0, AS)\}$ $\delta(q_0, \varepsilon, S)=\{(q_0, \varepsilon)\}$ $\delta(q_0, 1, A)=\{(q_0, AA)\}$ $\delta(q_0, 0, A)=\{(q_1, A)\}$ $\delta(q_0, 1, A)=\{(q_1, \varepsilon)\}$ $\delta(q_1, 0, S)=\{(q_0, S)\}$
   How to answer

   • Recall triplet construction $[q,X,p]$ for PDA to CFG
   • Create variables for states $q_0,q_1$ and stack symbols $S,A$
   • Translate each $\delta$ move into productions
   • List resulting CFG productions
10. 7 Marks
    aConstruct a PDA for all the strings, generating odd palindromes by empty stack over the alphabet $\Sigma = \{a, b\}^*$.
    How to answer

    • Define odd palindrome $ww^Rc$ form over $\{a,b\}$
    • Push first half, guess middle, pop and match second half
    • Define transitions for empty-stack acceptance
    • Show acceptance trace example
11. 7 Marks
    bDesign a Turing machine for the language $L = \{a^n b^n c^n / n \ge 1\}$.
    How to answer

    • Define tape alphabet and states for marking a,b,c
    • Describe loop: mark an $a$, then matching $b$, then matching $c$
    • Restore and check all symbols marked
    • Accept if $n\ge 1$ matched, else reject
12. 7 Marks
    aDiscuss about the Universal Turing Machine.
    How to answer

    • Define UTM as machine simulating any TM from its encoding
    • Explain encoding of states, tape symbols and transition table
    • Describe working: fetch-decode-execute cycle
    • Mention significance for stored program concept
13. 7 Marks
    bDefine PCP. Give the solution of PCP $X = (ba, ab, a, baa, b)$ and $Y = (bab, baa, ba, a, aba)$.
    How to answer

    • Define PCP with pairs $(x_i,y_i)$ and matching sequence
    • List given X=(ba,ab,a,baa,b) and Y=(bab,baa,ba,a,aba)
    • Show index sequence giving common string
    • Verify concatenated strings from X and Y are equal
14. 14 Marks
    Write short notes on any two of the following:

    1. a)Closure properties of Regular Language
    2. b)Chomsky hierarchy of grammar
    3. c)Petri Nets model
    4. d)P and NP Problems
    How to answer

    • Select any two topics from four options
    • Give definition, formal statement and example for each
    • Mention key theorems / properties / diagram where relevant
    • Conclude with significance in TOC