AL-601 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. 7 Marks
   aWhat is Moore Machine? How Moore machine can be converted into Mealy Machine? Explain with the help of an example.
   How to answer

   • Define Moore machine (output associated with states).
   • Define Mealy machine (output associated with transitions).
   • Steps for Moore to Mealy conversion (move state output to incoming transitions).
   • Illustrate with example transition table/diagram.
2. 7 Marks
   bDescribe how Finite automata can be called a language acceptor?
   How to answer

   • Define finite automaton as 5-tuple.
   • Explain input tape, reading and acceptance by final state.
   • Explain language accepted / language acceptor concept.
   • Give example of acceptance.
3. 7 Marks
   aExplain briefly about the composite machine with an example.
   How to answer

   • Define composite / product machine concept.
   • Explain construction combining two machines.
   • Give example e.g. combining two DFAs.
   • Mention application.
4. 7 Marks
   bFind out the Regular Expression from given DFA.

   

   How to answer

   • Write state equations using Arden's theorem / state elimination.
   • Eliminate q3 and q2 to get equation for q1.
   • Simplify to regular expression for final state q1.
   • State final regular expression.
5. 7 Marks
   aWhat do you mean by Closure properties of regular languages? Define some important closure properties.
   How to answer

   • Define closure property meaning.
   • List union, concatenation, Kleene star closure.
   • List intersection, complement, difference.
   • Brief proof idea using automata/regular expressions.
6. 7 Marks
   bObtain the regular expression for the following set:

   1. i)Set of all strings over $\Sigma = (a,b)$ with exactly two $a$.
   2. ii)$L = \{a^x \mid x \text{ is divisible by 3 or 5}\}$.
   How to answer

   • For (i) construct expression with exactly two a's: b* a b* a b*.
   • For (ii) use union of multiples of 3 and 5: (aaa)* + (aaaaa)* expanded.
   • Justify correctness of patterns.
   • Write final regular expressions.
7. 7 Marks
   aDifferentiate between Context-Free Grammar and Context-Sensitive Grammar.
   How to answer

   • Define CFG: productions A -> aA | ... and CSG: context-dependent.
   • Compare production form, expressive power, languages.
   • Compare automata (PDA vs LBA) and closure.
   • Give examples.
8. 7 Marks
   bShow that $L = \{a^n b^n c^n \mid n \ge 1\}$ is not CFL.
   How to answer

   • Assume L is CFL and apply pumping lemma for CFL.
   • Choose string a^n b^n c^n and decomposition uvwxy.
   • Show pumping violates equal counts.
   • Conclude L is not CFL (context-sensitive).
9. 7 Marks
   aWrite CFG for regular expression $(011 + 1)^*(01)^*$.
   How to answer

   • Introduce variables for (011+1)* and (01)* parts.
   • Write productions for 011, 1, 01 using concatenation.
   • Combine with start symbol S -> AB.
   • Present final CFG.
10. 7 Marks
    bDesign PDA to accept the language $L(G) = \{a^n b^m a^n \mid m,n \ge 1\}$
    How to answer

    • Define PDA 7-tuple and stack strategy.
    • Push first a^n, read b^m, match second a^n.
    • Give transition functions for each phase.
    • Show acceptance by empty stack/final state.
11. 7 Marks
    aDesign a PDA which recognizes the set of all even length palindromes over $\{a, b\}$.
    How to answer

    • Use non-determinism to guess middle of string.
    • Push first half symbols onto stack.
    • Pop and match second half in reverse.
    • Accept even-length palindromes on empty stack.
12. 7 Marks
    bWhat is PDA? Explain instantaneous description of PDA.
    How to answer

    • Define PDA as 7-tuple with stack.
    • Define instantaneous description (state, input, stack).
    • Explain move relation |- between IDs.
    • Give example of ID sequence.
13. 7 Marks
    aDesign a Turing Machine for the language $\{L(G) = a^n b^n \mid n \ge 1\}$
    How to answer

    • Define TM 7-tuple and tape strategy for a^n b^n.
    • Steps: mark a, find matching b, repeat and return.
    • Give transition diagram/table.
    • Show acceptance for n>=1.
14. 7 Marks
    bExplain P class problems in detail.
    How to answer

    • Define P as polynomial-time decidable problems.
    • Explain deterministic TM and polynomial bound.
    • Give examples (sorting, shortest path).
    • Mention relation to NP.
15. 14 Marks
    Write short note on any two of the following:

    1. i)NP Hard
    2. ii)Petri Net Model
    3. iii)Halting problem of Turing machine
    4. iv)2-way DFA
    How to answer

    • Select any two topics from i)-iv).
    • Give definition and key features for each.
    • Give example/diagram where applicable.
    • Mention significance in TOC.