IT-503-A 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. 7 Marks
   aCompute the Regular Expression for the DFA as shown below

   

   How to answer

   • Identify start state q0, final state q1, dead/trap state q2 from diagram
   • Apply state elimination / Arden's theorem to eliminate q2 and q1
   • Obtain regular expression for strings reaching final state
2. 7 Marks
   bDesign DFA's for detecting 1100 Sequence with Overlap over the alphabet $\Sigma = \{0, 1\}$.
   How to answer

   • Define states for progress of prefix of 1100 (5 states including trap/accept)
   • Define transition table for alphabet {0,1} with overlap handling
   • Present transition diagram and indicate final state for detection
3. 7 Marks
   aDesign a NFA that accepts the language over the alphabet, $\Sigma = \{0, 1, 2\}$ where the decimal equivalent of the language is divisible by 4
   How to answer

   • Use remainder modulo 4 as states (0,1,2,3) for base-3 numbers
   • Define transitions: new_remainder = (old*3 + digit) mod 4
   • Mark remainder 0 as final state and show NFA diagram
4. 7 Marks
   bIdentify the language, L generated by the following grammar, G $G = (\{S, A, B\}, \{a, b\}, \{S \to Aaa, A \to aa | B, B \to bbB | bb\}, S)$.
   How to answer

   • Expand productions S -> Aaa, A -> aa | B, B -> bbB | bb
   • Derive form of strings: prefix from A plus suffix aaa
   • Identify language as {aaaa} union {bb^n aa?} - formalize as set
5. 7 Marks
   aConvert the following NFA to an equivalent DFA.

   

   How to answer

   • Compute lambda-closures for states q0,q1,q2,q3
   • Construct subset construction transition table for inputs a,b
   • Draw equivalent DFA with reachable subsets as states
6. 7 Marks
   bFind a regular grammar that generates the language on $\{a, b\}$ consisting of all strings with at most one a's and more than two b's.
   How to answer

   • Interpret constraint: at most one a and more than two b's
   • Design DFA / regular expression for the constraint
   • Convert to regular grammar productions with nonterminals
7. 7 Marks
   aConstruct context free grammars to accept the language $L(G) = \{a^n b^m c^m d^{2n} | n \ge 0, m > 0\}$ over the alphabet, $\Sigma = \{a, b, c, d\}$
   How to answer

   • Handle inner b^m c^m with one nonterminal (m>0)
   • Wrap with outer a^n ... d^{2n} with another nonterminal (n>=0)
   • Combine productions with start symbol S
8. 7 Marks
   bConstruct Non-Deterministic Pushdown Automata (NPDA) to accept the language $\{w | w \text{ starts and ends with the same symbol}\}$ over the alphabet, $\Sigma = \{0, 1\}$
   How to answer

   • Guess first symbol and push it onto stack
   • Skip middle part while staying in loop state
   • Match last symbol with stored first symbol and accept
9. 7 Marks
   aConstruct Turing Machine (TM) to accept the language $L = \{0^{2n} 1^n 2^{2n} | n >= 0\}$ over the alphabet, $\Sigma = \{0, 1, 2\}$
   How to answer

   • Use tape to mark and match 2 zeros with 1 one and 2 twos
   • Define states for scanning and crossing off symbols
   • Accept when all symbols matched, reject otherwise
10. 7 Marks
    bConstruct corresponding CFG for the following NPDA.

    

    How to answer

    • Read NPDA transitions at q0 and q1 with push/pop actions
    • Apply standard NPDA to CFG triplet construction
    • Simplify to equivalent CFG productions
11. 7 Marks
    aGive a Deterministic PDA that accepts $\{a^n b^m : m \ge n + 2\}$ over the alphabet, $\Sigma = \{a, b\}$
    How to answer

    • Push a's onto stack, then pop one a per b with extra check
    • Ensure at least two extra b's remain after matching
    • Define deterministic transitions and accept by empty stack/final state
12. 7 Marks
    bGive an NPDA that simulates the following grammar (S is start symbol): $S \to aABB | aAA$ $A \to aBB | a$ $B \to bBB | A$
    How to answer

    • Start with push of start symbol S
    • For each variable expand by pushing RHS nondeterministically
    • For terminals match with input and pop; accept on empty stack
13. 7 Marks
    aProve that the problem of determining whether for a Turing machine M there is some input string for which M halts is undecidable.
    How to answer

    • Assume decider for existence of halting input
    • Reduce halting problem to this problem
    • Conclude undecidability by contradiction
14. 7 Marks
    bProve that the recursive languages are closed under union, intersection, and complement.
    How to answer

    • Construct TM for union using parallel simulation of M1,M2
    • Construct TM for intersection similarly
    • Construct TM for complement by swapping accept/reject for deciders
15. 14 Marks
    Given the following ambiguous context free grammar $S \to Ab | aaB$ $A \to a | Aa$ $B \to b$

    1. i)Find the string s generated by the grammar that has two leftmost derivations. Show the derivations.
    2. ii)Show the two derivation trees for the string S.
    3. iii)Find an equivalent unambiguous context-free grammar.
    4. iv)Give the unique leftmost derivation and derivation tree for the string s generated from the unambiguous grammar above.
    How to answer

    • Find ambiguous string e.g. aab by two leftmost derivations
    • Draw two distinct parse/derivation trees for s
    • Rewrite grammar to remove ambiguity and give unique derivation