AL-601 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
   aDefine finite automata and list the features of finite automata with an example.
   How to answer

   • Formal 5-tuple definition (Q, Sigma, delta, q0, F)
   • Explanation of components and transition function
   • Key features: finite states, deterministic/nondeterministic, no memory, etc.
   • Example automaton with diagram and accepted language
2. 7 Marks
   bDesign a finite automata with Sum = {0,1} accepts those strings which starts with 1 and ends with 0.
   How to answer

   • Alphabet Sigma = {0,1}, start state and trap/dead state concept
   • Construction for starts with 1 and ends with 0 (minimum 2 symbols)
   • Transition table/diagram with 4 states
   • Verification with example strings
3. 7 Marks
   aDifferentiate between Mealy and Moore machines with a suitable example.
   How to answer

   • Definition of Mealy (output on transition) vs Moore (output on state)
   • Comparison table: output timing, states required, etc.
   • Example transducer for each
   • Diagram of both machines
4. 7 Marks
   bDesign a regular expression for the following DFA.

   

   How to answer

   • Interpret given DFA transition table with start Q1 and final Q2
   • Apply state elimination / Arden's theorem to obtain equations
   • Solve for language accepted (strings ending pattern)
   • Write final regular expression
5. 14 Marks
   Consider the following NFA with epsilon:

   1. i)Compute the $\epsilon$-closure of each state.
   2. ii)Give all the strings of length 4 or less accepted by the automation.
   3. iii)Convert the automation to DFA.

   

   How to answer

   • Compute epsilon-closure for P, Q, R using epsilon (E) transitions
   • Enumerate strings length <=4 over {A,B,c} reaching final state *R
   • Subset construction to convert epsilon-NFA to DFA
   • DFA transition table and final states
6. 7 Marks
   aShow that the languages $L=\{0^n1^m / n = m \text{ and } n \ge 1\}$ is deterministic context free language.
   How to answer

   • Define deterministic PDA / DCFL concept
   • Construct DPDA for $L=\{0^n1^n/n\ge 1\}$ using stack to match counts
   • Argue determinism: at most one move per configuration
   • Conclude L is deterministic context-free
7. 7 Marks
   bDefine parse tree and construct a parse tree for the string 'abaabb' from the following given grammar. $S \rightarrow SS/aSb/\epsilon$
   How to answer

   • Define parse tree: derivation tree from grammar
   • Apply productions S -> SS / aSb / epsilon to derive 'abaabb'
   • Draw hierarchical parse tree with leaves abaabb
   • Show yield matches string
8. 7 Marks
   aConvert the given CFG into GNF: $S \rightarrow ABA/AB/BA/AA/B$ $A \rightarrow aA/a$ $B \rightarrow bB/b$
   How to answer

   • Remove epsilon/unit productions and simplify given CFG
   • Convert to Chomsky normal form as intermediate
   • Convert to Greibach Normal Form: A -> a alpha form
   • List final GNF productions
9. 7 Marks
   bDefine pushdown automata and explain its model with a neat sketch.
   How to answer

   • Formal 7-tuple definition of PDA
   • Explain components: states, input, stack, transitions
   • Neat labelled sketch of PDA model with input tape, control, stack
   • Working of push/pop with example
10. 7 Marks
    aConstruct a PDA for the given language $L = \{ WW^R / W \in \{a,b\}^* \}$.
    How to answer

    • Idea: push W, guess middle, pop against W^R
    • Define states, stack alphabet and transitions
    • Show acceptance by final state/empty stack
    • Test with example ww^R
11. 7 Marks
    bConvert the following grammar into PDA which accepts the same language by empty stack. $S \rightarrow 0S1/A$ $A \rightarrow 1A0/S/\epsilon$
    How to answer

    • Standard construction from CFG to PDA with 3 states
    • Transitions for variables and terminals with empty-stack acceptance
    • Apply to S -> 0S1/A, A -> 1A0/S/epsilon
    • List resulting PDA delta
12. 7 Marks
    aDesign a turing machine over {0, 1} for the language $L = \{W/W \text{ is a multiple of 3 }\}$.
    How to answer

    • Interpret W as binary number multiple of 3 (states for remainder 0,1,2)
    • Define TM transitions moving right computing remainder
    • Accept in remainder-0 state
    • State diagram/table of TM
13. 7 Marks
    bFind whether the post correspondence problem $P = \{(ba, bab), (abb, bb), (bab, abb)\}$ has a match? Explain in detail.
    How to answer

    • Define Post Correspondence Problem and match condition
    • Attempt to build correspondence sequence from given pairs
    • Show whether sequence yields same top/bottom string
    • Conclude match exists or not with reasoning
14. 14 Marks
    Write a short note on any two of the following

    1. a)Arden's theorem
    2. b)Chomsky hierarchy of the grammar
    3. c)NPDA
    4. d)N-P Complete problem
    How to answer

    • Choose any two topics with definition and statement
    • Explain key theorem/steps with example
    • Relevant diagram/hierarchy or proof sketch
    • Applications and significance