CS-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
   aDraw a DFA to accept string of 0's and 1's not ending with the string 01.
   How to answer

   • Define DFA 5-tuple and acceptance condition for complement of suffix 01
   • Construct states tracking last symbols: start/no-01-ending, seen-0, trap for ending-01
   • Give transition table for 0,1 and mark accepting vs non-accepting states
   • Show state diagram and argue correctness with examples
2. 7 Marks
   bDesign a DFA to accept string of 0's and 1's when interpreted as binary numbers would be multiple of 3.
   How to answer

   • Use remainders 0,1,2 modulo 3 as three states with 0 as start and accept
   • Apply transition delta(q,r) on bit b = (2*r + b) mod 3
   • Give full transition table/diagram
   • Test with examples e.g. 0, 11 (=3), 110 (=6)
3. 7 Marks
   aFind the context free grammar with no useless symbols equivalent to $S \to AB/Ca, B \to BC/AB, A \to a, C \to aB/b$
   How to answer

   • Identify generating and reachable symbols from S -> AB/Ca etc.
   • Remove non-generating / non-reachable productions step by step
   • Rewrite reduced grammar with only useful symbols
   • Verify language preserved
4. 7 Marks
   bDerive regular expression from this finite automata.

   

   How to answer

   • Write state equations R_q using Arden's theorem for q0,q1,q2
   • Eliminate q2 and q0 to solve for final state q2
   • Simplify regular expression
   • State final RE for strings reaching q2
5. 7 Marks
   aWhat is meant by ambiguous grammar? Test whether the grammar is ambiguous or not $S \to SS/a/b$
   How to answer

   • Define ambiguous grammar: two distinct parse trees/leftmost derivations
   • Give two derivations/trees for a string e.g. aab using S->SS/a/b
   • Conclude grammar is ambiguous
   • Mention removal if needed
6. 7 Marks
   bConstruct an equivalent FA for the given regular expression $(0+1)^{*}(00+11)(0+1)^{*}$
   How to answer

   • Interpret RE (0+1)*(00+11)(0+1)* as containing 00 or 11
   • Design NFA then convert to DFA via subset construction
   • Give transition diagram with trap/accept states
   • Justify acceptance of strings containing double 0 or double 1
7. 14 Marks
   Construct the following CFG grammar

   1. i)$a^{n} b^{m} c^{n}$ where $m, n \ge 1$
   2. ii)Obtain a CFG to generate a integer
   How to answer

   • Give CFG productions for a^n b^m c^n with matched a,c and independent b
   • Give CFG for signed/unsigned integer (digits, optional sign)
   • Present in 4-tuple form if required
   • Show sample derivations
8. 14 Marks
   Construct the PDA accepting the language.

   1. i)$L = \{(ab)^{n} \mid n >= 1\}$ by empty stack.
   2. ii)$L = \{ww^{R} \mid w \text{ is in } (a+b)^{*}\}$ by empty stack.
   3. iii)$L = \{a^{2n} b^{n} \mid n >= 1\}$ by empty stack.
   How to answer

   • Define PDA 7-tuple and empty-stack acceptance
   • Give transitions pushing for first half and popping for second half for each L
   • Handle (ab)^n, ww^R over (a+b)*, and a^{2n} b^n
   • Trace acceptance on example string
9. 7 Marks
   aLet G be the grammar given by $S \to aABB/aAA, A \to aBB/a, B \to bBB/A$ construct the PDA that accepts the language generated by this grammar G.
   How to answer

   • Use standard CFG-to-PDA construction with single state pushing start symbol
   • Add transitions for S->aABB/aAA, A->aBB/a, B->bBB/A
   • Explain push/pop on terminals vs variables
   • Show acceptance of sample string
10. 7 Marks
    bDefine the context free grammars in the 4 tuple from (V, T, P, S) for the given languages on $\Sigma(a, b)$.

    1. i)All strings having atleast two 'a's.
    2. ii)All possible strings not containing triple 'b's.
    How to answer

    • Define CFG as (V,T,P,S) over Sigma={a,b}
    • Give productions for at least two a's: e.g. S->XaXaX
    • Give productions avoiding bbb using states for 0,1,2 consecutive b's
    • List V,T,P,S explicitly
11. 7 Marks
    aWhat is the difference between a recursive and recursively enumerable languages?
    How to answer

    • Define recursive = decided by halting TM; RE = semi-decided/accepted by TM
    • Compare closure and complement properties
    • Give examples: Halting language is RE but not recursive
    • Tabulate differences
12. 7 Marks
    bWhat do you mean by saying that the halting problem of TM is undecidable?
    How to answer

    • State halting problem: decide if TM halts on given input
    • Outline diagonalization/reduction proof of undecidability
    • Explain no total TM can decide it
    • Mention implication for decidability
13. 14 Marks
    Write short notes on : (Any three)

    1. i)Post correspondence problem
    2. ii)Halting problem
    3. iii)Closure property of regular grammar
    4. iv)Turing machine
    How to answer

    • Define each: PCP, Halting problem, closure properties, TM model
    • Give formal statement/example and significance
    • Mention decidability/undecidability results
    • Conclude with applications