CS-501 Theory of Computation - May 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. 14 Marks
   Convert the following Moore machine to Mealy.

   1. i)Moore machine (i) with states $q_0/0$, $q_1/1$ as shown in figure.
   2. ii)Moore machine (ii) with states $q_0/0$, $q_1/1$ as shown in figure.

   

   How to answer

   • Recall Moore to Mealy conversion rule: Mealy output on transition equals output of destination Moore state
   • Transfer transitions for both machines (i) and (ii) with inputs a,b
   • Draw Mealy transition diagram with output labels a/0, a/1 etc.
   • Verify equivalence on sample strings
2. 14 Marks
   aFor $\Sigma = \{a, b\}$, construct DFA's that accept the sets consisting of

   1. i)All the strings with exactly one 'a'.
   2. ii)All the string with atleast one 'a'.
   3. iii)All strings with atleast one 'a' and followed by exactly two b's.
   How to answer

   • Define DFA 5-tuple for each language
   • Design states tracking count of a's (0,1,>1) and b's
   • Draw transition diagrams for (i), (ii), (iii)
   • Identify accept states
3. 14 Marks
   Describe the following sets by regular expression.

   1. i)Strings containing 1100 as substrings.
   2. ii)The set of all strings of 0's are 1's ending with 00. .........}.
   3. iii)$\{\Lambda, a, aa, aaa, aaaa, .....................$
   How to answer

   • Recall regular expression operators *, +, concatenation
   • Write $(0+1)^*1100(0+1)^*$ for substring 1100
   • Write $(0+1)^*00$ for ending with 00
   • Write $a^*$ for {Lambda,a,aa,...}
4. 7 Marks
   aExplain Arden's theorem and Pumping Lemma.
   How to answer

   • State Arden's theorem: R = Q + RP implies R = QP*
   • Give assumptions and proof steps
   • State pumping lemma for regular languages with |xy| conditions
   • Explain use to prove non-regularity
5. 7 Marks
   bWhat is Ambiguity? Explain taking any two examples.
   How to answer

   • Define ambiguity: grammar with two distinct parse trees/leftmost derivations
   • Give example 1 with derivations and parse trees
   • Give example 2 with derivations and parse trees
   • Conclude ambiguous vs unambiguous
6. 7 Marks
   aDesign a CFG.

   1. i)$L(G)= \{a^ib^jc^k \mid i \neq j \text{ (or) } j \neq k\}$
   2. ii)$L(G_I)= \{a^ib^{2i} \mid i \geq 0\}$
   How to answer

   • Recall CFG construction for unequal exponents using union
   • Give productions for i!=j part and j!=k part
   • Give productions S -> aSb | aA | bB style for a^i b^{2i}
   • Verify with derivations
7. 7 Marks
   bDefine a context free grammar with example.
   How to answer

   • Define CFG 4-tuple (V,T,P,S)
   • Explain productions with example grammar
   • Show derivation of sample string
   • Show parse tree
8. 7 Marks
   aExplain DPDA and NPDA with taking a suitable example.
   How to answer

   • Define DPDA: at most one move per configuration
   • Define NPDA: multiple choices allowed
   • Give example language for DPDA e.g. deterministic
   • Give example requiring nondeterminism e.g. ww^R
9. 7 Marks
   bExplain Recursively enumerable language and decidability.
   How to answer

   • Define recursively enumerable language via Turing machine acceptance
   • Distinguish recursive vs RE languages
   • Define decidability and decidable problem
   • Give examples of decidable/undecidable
10. 14 Marks
    Design a Push down automata.

    1. i)$a^nb^{3n}, n \geq 1$
    2. ii)$ww^R, w \in (a, b)^2$
    How to answer

    • Define PDA 7-tuple and stack operations
    • Design PDA for $a^nb^{3n}$ pushing 3 symbols per a
    • Design NPDA for $ww^R$ guessing middle
    • Give transition functions and diagrams
11. 14 Marks
    Write short notes on: (Any three)

    1. i)Halting problem
    2. ii)Turing machine
    3. iii)Chomsky Normal form
    4. iv)2 way DFA
    How to answer

    • Define each selected concept briefly
    • Give formal definition / construction
    • Give example / diagram where applicable
    • Mention significance / application