IT-503-A Theory of Computation - Jun 2025 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
   aConstruct a NFA second last symbol is zero over the alphabet $(0, 1)$ than convert in DFA?
   How to answer

   • Define NFA with 3-4 states for second-last symbol 0 over {0,1}
   • Show NFA transition table/diagram
   • Apply subset construction to get DFA states
   • Show DFA transition table/diagram and final states
2. 7 Marks
   bDesign a DFA to accept string of 0's and 1's when interpreted as binary numbers would be multiple of 4.
   How to answer

   • Interpret binary value modulo 4
   • Use 4 states for remainders 0,1,2,3
   • Define transitions on 0 as 2*r mod 4 and on 1 as 2*r+1 mod 4
   • Mark remainder-0 state as final with diagram
3. 7 Marks
   aWrite CFG to accept the language defined by, $L \{a^i b^j c^k \, i \, j \, k, >= 0, i = j + k.$
   How to answer

   • Interpret condition $i=j+k$ for $a^i b^j c^k$
   • Split into $a^j b^j$ and $a^k c^k$ parts
   • Give productions e.g. S -> AB, A -> aAb|epsilon, B -> aBc|epsilon
   • Verify with example strings
4. 7 Marks
   bDerive Regular Expression from this Finite Automata.

   

   How to answer

   • Write state equations for q0 and q1
   • Apply Arden's theorem / state elimination
   • Eliminate q1 using self-loop 1
   • Obtain final regular expression for accepted language
5. 7 Marks
   aHow $\epsilon$-productions are eliminated from a grammar whose language doesn't have empty string? Remove $\epsilon$-productions from the grammar given below. $S \to a|aA|B|C, A \to aB | \epsilon, B \to Aa, C \to aCD,$ $D \to ddd$
   How to answer

   • Define nullable variables and epsilon-productions
   • Compute nullable set: A nullable, then B, S nullable
   • Add productions with nullable occurrences omitted
   • Write final epsilon-free grammar
6. 7 Marks
   bConstruct an equivalent FA for the given regular expression $(101)^*(01 + 11)(10 + 10)^*$
   How to answer

   • Break expression $(101)^*(01+11)(10+10)^*$ into three parts
   • Construct NFA using Thompson construction for each part
   • Concatenate the three automata
   • Convert to DFA/FA if required and show final diagram
7. 14 Marks
   Consider the following productions, $S \to aB|bA, A \to aS|bAA|a, B \to bS|aBB|b$ For the string aabbabbba, find the :

   1. i)Leftmost derivation
   2. ii)Rightmost derivation
   3. iii)Parse Tree
   How to answer

   • Start from S and repeatedly replace leftmost variable to get aabbabbba
   • Start from S and repeatedly replace rightmost variable to get same string
   • Draw parse tree with S,A,B as interior nodes and terminals as leaves
   • Verify yield equals aabbabbba
8. 14 Marks
   Construct the PDA accepting the language.

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

   • Describe PDA model and acceptance by empty stack
   • Give transitions pushing a's and popping on b's for each language
   • Handle center marker C for wCw^R
   • Show stack behavior for sample strings
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

   • Recall CFG to PDA construction using stack
   • Create PDA states q0,q1,q2 with push of start symbol
   • Add transitions for productions S->aABB/aAA etc.
   • Show acceptance of generated language
10. 7 Marks
    bDefine ambiguous grammar. Show that the following grammar is ambiguous $S \to aSbS | bSaS | \epsilon$
    How to answer

    • Define ambiguous grammar with two parse trees/derivations
    • Take string from S->aSbS|bSaS|epsilon e.g. abab
    • Show two distinct leftmost derivations/parse trees
    • Conclude grammar is ambiguous
11. 7 Marks
    aWhat is the difference between a recursive and recursively enumerable Languages?
    How to answer

    • Define recursive language with halting TM deciding membership
    • Define recursively enumerable with TM enumerating/accepting
    • Compare decidability vs semi-decidability
    • Give examples e.g. halting language for RE but not recursive
12. 7 Marks
    bWhat are NP-complete and NP-hard problems? Explain them with examples.
    How to answer

    • Define NP, NP-hard via polynomial reduction
    • Define NP-complete as NP and NP-hard
    • Explain reducibility with examples SAT, TSP, clique
    • Distinguish with diagram of complexity classes
13. 14 Marks
    Write a short notes (any three):

    1. i)Decidability
    2. ii)Universal Turing Machine
    3. iii)2 Way DFA
    4. iv)Petrinet Model
    How to answer

    • Define decidability with decider TM
    • Describe universal Turing machine simulating any TM
    • Explain 2-way DFA head movement
    • Describe Petri net places, transitions, tokens with example