AL-601 Theory of Computation - Dec 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
   aDesign a Moore machine to determine the residue of mod 2 of the input treated as a binary string.
   How to answer

   • Define states for remainder 0 and 1 with output 0/1
   • Show transition on binary input 0/1 updating mod 2 value
   • Give transition table and state diagram
2. 7 Marks
   bFind an equivalent $\epsilon$-NFA for the following regular expression $(0+1)^*011$.
   How to answer

   • Recall Thompson construction for union, concat, star
   • Construct epsilon-NFA for $(0+1)^*$ then for $011$
   • Combine and simplify with epsilon transitions
3. 7 Marks
   aConvert the $\Lambda$-NFA to NFA.

   

   How to answer

   • Compute Lambda-closure of each state
   • Compute NFA transitions on 0 and 1 without Lambda
   • Give resulting NFA transition table and diagram
4. 7 Marks
   bConvert the grammar $\{S \to ABaC|ABa, A \to Aa|a, B \to BaB|b, C \to CC\}$ Chomsky normal form.
   How to answer

   • Eliminate unit and useless productions and convert terminals to variables
   • Break long productions $S \to ABaC$ etc. into binary form
   • Introduce new variables and give final CNF productions
5. 7 Marks
   aDefine formally Type 0, Type 1, Type 2 and Type 3 grammar. Show the corresponding automata for each class.
   How to answer

   • Give formal tuple definition for Type 0,1,2,3 grammars with restrictions
   • State Chomsky hierarchy inclusion
   • Map to Turing machine, LBA, PDA, finite automata
6. 7 Marks
   bConstruct PDA for the language $wcw^R$ where $w$ is string of zeroes and ones.
   How to answer

   • Push w symbols onto stack
   • Read center marker c without stack change
   • Pop and match with w^R and accept
7. 7 Marks
   aDerive regular expression from this Finite Automata.

   

   How to answer

   • Apply state elimination or Arden theorem to given DFA
   • Eliminate q2 then q1 to get expression
   • Simplify final regular expression
8. 7 Marks
   bDefine regular language and regular expressions. Find regular expression for the following : Language of all string that do not end with 01.
   How to answer

   • Define regular language and regular expression operators
   • Complement language of strings ending with 01
   • Write expression e.g. (0+1)*(00+10+0+epsilon) and justify
9. 14 Marks
   Construct a PDA accepting by empty stack each of the following language.

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

   • Define PDA by empty stack acceptance
   • Give construction for a^n b^n c^m d^m using stack counting
   • Give construction for a^3 b^n with stack counting
10. 7 Marks
    aConvert to Greibach normal form. $\{S \to AB, A \to SA|AA|a, B \to SB|b\}$
    How to answer

    • Order variables and eliminate left recursion
    • Ensure productions start with terminal
    • Introduce new variables to get GNF form
11. 7 Marks
    bDerive any two representative strings with minimum length 4 from following context free grammar. $G = (\{S, A, B\}, \{a, b\}, P, S)$ $S \to bA | aB$ $A \to bAA | aS | a$ $B \to aBB | bS | b$
    How to answer

    • Interpret productions of G with start S
    • Derive two distinct terminal strings of length >=4 step by step
    • Show leftmost/rightmost derivation trees
12. 7 Marks
    aDesign a Turing Machine that accepts the language $1^n 0^n$ where $n > 0$.
    How to answer

    • Explain tape, head, matching 1s with 0s by marking
    • Give state transitions for scanning and crossing
    • Show acceptance when all symbols matched
13. 7 Marks
    bWhat is a Turing machine? Give the specification of a Turing machine and explain.
    How to answer

    • Define 7-tuple specification of Turing machine
    • Explain tape, finite control, transition function
    • Give example movement and operation
14. 14 Marks
    Write a short note (any three):

    1. i)Recursively Enumerable
    2. ii)GNF
    3. iii)Derivation Tree
    4. iv)Melay Machine
    How to answer

    • Define each chosen topic formally
    • Give example/automata or grammar illustration
    • Mention significance and application