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

   

   How to answer

   • Identify start state A, intermediate B, final C.
   • Apply state elimination / Arden's theorem step by step.
   • Obtain regular expression for strings reaching C.
   • Simplify expression.
2. 7 Marks
   bDesign DFA's for detecting 1001 Sequence without Overlap over the alphabet $\Sigma = \{0, 1\}$
   How to answer

   • Define states for prefixes of 1001 and non-overlapping reset.
   • Define transition table for alphabet {0,1}.
   • Draw DFA with trap/dead handling after detection.
   • Explain non-overlapping behavior.
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 3.
   How to answer

   • Use remainders 0,1,2 modulo 3 as states.
   • Define transition on digit d as new_remainder = (old*10 + d) mod 3.
   • Mark remainder 0 state as accepting.
   • Show NFA (DFA) diagram.
4. 7 Marks
   bIdentify the language, L generated by the following grammar, G: $G = (\{S, A, B\}, \{a, b\}, \{S \to Aa, A \to a|B, B \to bB|b\}, S)$.
   How to answer

   • Expand productions S -> Aa, A -> a|B, B -> bB|b.
   • Derive general sentential forms.
   • Identify pattern b^n a a or similar.
   • State language L in set notation.
5. 7 Marks
   aConvert the following NFA to an equivalent DFA.

   

   How to answer

   • Compute lambda-closure of start state 1 including state 4.
   • Apply subset construction for inputs a and b.
   • Construct transition table for reachable subsets.
   • Draw equivalent DFA and mark accepting subsets containing 6.
6. 7 Marks
   bFind a regular grammar that generates the language on {a,b} consisting of all strings with exactly one a's and no more than two b's.
   How to answer

   • Enumerate allowed strings: exactly one a and 0-2 b's.
   • Define nonterminals for count of b's before/after a.
   • Write regular (right-linear) productions.
   • Verify generation.
7. 7 Marks
   aConstruct context free grammars to accept the language $L = \{a^{n+2} b^{m+1} \mid n = m\}$ over the alphabet, $\Sigma = \{a, b\}$
   How to answer

   • Rewrite condition n=m as L = {a^{n+2} b^{n+1} | n>=0}.
   • Introduce variable generating matched a^n b^n core.
   • Add extra fixed a's and b.
   • Give productions e.g. S -> aAb with base.
8. 7 Marks
   bConstruct Non-Deterministic Pushdown Automata (NPDA) to accept the language $L = \{0^{n+1}1^{2n} \mid n >= m\}$ over the alphabet, $\Sigma = \{0, 1\}$
   How to answer

   • Define stack alphabet and push 0's.
   • On reading 1's pop or count double.
   • Use nondeterminism for n>=m condition as printed.
   • Define accept by empty stack / final state.
9. 7 Marks
   aConstruct Turing Machine (TM) to accept the language $L = \{0^{n} 1^{n} 2^{n} \mid n >= 0\}$ over the alphabet, $\Sigma = \{0, 1, 2\}$
   How to answer

   • Describe tape alphabet and marking strategy for 0,1,2.
   • Give state transitions to match one of each symbol.
   • Handle n=0 (empty) acceptance.
   • Show acceptance by halting in final state.
10. 7 Marks
    bConstruct corresponding CFG for the following NPDA.

    

    How to answer

    • List NPDA states and stack operations from diagram.
    • Apply standard NPDA-to-CFG triplet construction.
    • Generate productions for push/pop pairs.
    • Simplify to equivalent CFG.
11. 7 Marks
    aGive a Deterministic PDA that accepts $\{a^{m} b^{n} c^{n} \mid m,n \geq 0\}$ over the alphabet, $\Sigma = \{a, b, c\}$.
    How to answer

    • Push a's then match b's with c's or skip.
    • Use stack to count n for b^n c^n.
    • Allow arbitrary m a's without stack change.
    • Define deterministic transitions and acceptance.
12. 7 Marks
    bGive an NPDA that simulates the following grammar (S is start symbol): $S \to aBB \mid cDD$ $B \to cD \mid aS$ $D \to dD \mid d$
    How to answer

    • Use standard CFG-to-NPDA construction with single state.
    • Push start symbol S then expand productions.
    • Match terminals against input.
    • Show simulation for given S,B,D productions.
13. 7 Marks
    aShow that the following language on $\Sigma = \{a, b, c\}$ is not context-free. $L = \{a^{i} b^{2i} a^{i} \mid i \geq 0\}$
    How to answer

    • Assume L context-free and apply pumping lemma.
    • Choose suitable string a^p b^{2p} a^p.
    • Show pumped decomposition violates form.
    • Conclude L not context-free.
14. 7 Marks
    bProve that a language $L$ is recursive if and only if $L$ and $\overline{L}$ are recursively enumerable.
    How to answer

    • Define recursive and recursively enumerable.
    • Prove forward: recursive implies both L and complement r.e.
    • Prove reverse: dovetail enumerators for L and complement.
    • Conclude equivalence.
15. 7 Marks
    aProve that there is no algorithm that determines whether an arbitrary Turing Machine halts when run with the input string 101.
    How to answer

    • Assume decider for halting on 101 exists.
    • Reduce general halting problem to this fixed-input case.
    • Derive contradiction via diagonalization / universality.
    • Conclude undecidability.
16. 7 Marks
    bProve that the problem of determining whether for a Turing machine M the language L(M) is regular is undecidable.
    How to answer

    • State Rice's theorem / reduction from halting.
    • Construct TM whose language is regular iff original halts.
    • Show decidability would solve halting.
    • Conclude regularity problem undecidable.