AL-601 Theory of Computation - May 2024 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
   aSay whether the NFA accepts the following or not

   1. i)abaa
   2. ii)abab

   

   How to answer

   • Describe NFA transitions from diagram with states q0, q1, q2
   • Trace computation paths for string abaa to check acceptance
   • Trace computation paths for string abab to check acceptance
   • Conclude accept / reject for each string
2. 7 Marks
   bConstruct a NFA second last symbol is zero over the alphabet $(0, 1)$ than convert in DFA.
   How to answer

   • Design 3-state NFA for second-last symbol 0 over {0,1}
   • Show NFA transition diagram
   • Convert using subset construction to DFA
   • Show resulting DFA diagram and explain
3. 7 Marks
   aExplain 'Finite State Machines with Outputs'. Discriminate between Mealy and Moore machines.
   How to answer

   • Define finite automata with output: input, state, output alphabets
   • Explain general model with output function
   • Define Mealy machine with example
   • Define Moore machine with example and differences
4. 7 Marks
   bDesign a DFA which accept the string starting symbol differ from ending symbol over the alphabet $\{0, 1\}$. Show dead state if any.
   How to answer

   • Define language where first and last symbols differ over {0,1}
   • Design DFA states tracking first symbol and acceptance
   • Show transition diagram with dead state
   • Verify with example strings
5. 14 Marks
   Minimize the following automata

   

   How to answer

   • Separate final and non-final states into partitions
   • Iteratively split partitions on 0 and 1 transitions
   • Identify equivalent states q1,q2 etc.
   • Construct minimized DFA transition table/diagram
6. 7 Marks
   aConstruct context free grammar for $L = \{wcw^R \mid w \text{ in } (a+b)^*\}$, Reverse of $w$ is denoted as $w^R$.
   How to answer

   • Define language L = {wcw^R | w in (a+b)*}
   • Give productions S -> aSa | bSb | c
   • Explain how center marker c and mirroring works
   • Show example derivations
7. 7 Marks
   bDefine a deterministic PDA. How a DPDA differs from a non-deterministic PDA?
   How to answer

   • Define DPDA with determinism condition on transition
   • Define NPDA with choice
   • Compare on transition function, acceptance power, language class
   • Give example language accepted by NPDA but not DPDA
8. 7 Marks
   aFind the Greibach normal form grammar equivalent to the following: CFG: $S \to AB$ $A \to BS \mid 1$ $B \to SA \mid 0$
   How to answer

   • Eliminate unit productions and convert to CNF-like form
   • Introduce new variables to ensure A -> a alpha form
   • Apply GNF conversion steps to given S,A,B productions
   • Present final GNF grammar and verify equivalence
9. 7 Marks
   bWhat do you mean by Parsing? How left most and right most derivation helps to find out the ambiguity in a grammar?
   How to answer

   • Define parsing and its role in syntax analysis
   • Define leftmost and rightmost derivations with example
   • Explain how two distinct parse trees show ambiguity
   • Conclude how derivations detect ambiguity
10. 14 Marks
    Construct a PDA accepting by empty stack each of the following language.

    1. i)$a^n b^m c^n$ where $n, m \ge 1$
    2. ii)$a^n b^{3n}$ $n \ge 0$
    How to answer

    • Describe PDA by empty stack model for given languages
    • Give stack operations to match a^n with c^n skipping b^m
    • Give stack operations to match a^n with b^{3n}
    • Present transition functions and acceptance logic
11. 7 Marks
    aDesign a Turing Machine which computes the multiplication of two numbers.
    How to answer

    • Describe TM model for multiplication (unary representation)
    • Outline algorithm: copying, repeated addition
    • Give state transitions / block diagram
    • Explain halting with product on tape
12. 7 Marks
    bState pumping lemma for regular languages. Prove that the language $\{a^n\}$ is not regular. Where $n$ is prime number.
    How to answer

    • State pumping lemma for regular languages with |xy|<=p condition
    • Assume L={a^n : n prime} regular and choose pumping string
    • Show pumped strings give non-prime length contradiction
    • Conclude L is not regular
13. 14 Marks
    Write short note on (any three):

    1. i)Halting problem
    2. ii)Decidability
    3. iii)Mealy Machine
    4. iv)CNF
    How to answer

    • Define each chosen topic with formal definition
    • Explain key concept / construction / significance
    • Give example or diagram where applicable
    • Mention applications or limitations