IT-503-A 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
   aWhat are the components of finite automata model?
   How to answer

   • Define 5-tuple (Q, Sigma, delta, q0, F)
   • Role of finite set of states, input alphabet, transition function
   • Start state and set of final/accepting states
   • Diagram of FA model block
2. 7 Marks
   bConstruct deterministic finite automata to recognize odd number of 1's and even number of 0's.
   How to answer

   • Take 4 states for parity of 0s and 1s: (even-even, even-odd, odd-even, odd-odd)
   • Define transitions on 0 toggling 0-parity, on 1 toggling 1-parity
   • Mark odd-1s and even-0s state as final
   • Draw DFA transition diagram
3. 7 Marks
   aConvert the Regular expression $(a+b)^*abb$ directly into a DFA.
   How to answer

   • Construct NFA/epsilon-closure or syntax tree for $(a+b)^*abb$
   • Apply subset construction / direct DFA method with positions
   • Obtain minimal 4-state DFA for suffix abb
   • Show transition table and diagram
4. 7 Marks
   bConsider the FA and construct regular expressions that are accepted by it.

   

   How to answer

   • Identify states, start A, final C, alphabet {0,1}
   • Apply Arden's theorem / state elimination
   • Solve equations for R_A, R_B, R_C, R_D
   • Write final regular expression for strings reaching C
5. 7 Marks
   aShow $id + id * id$ can be generated by two distinct leftmost derivative in the grammar. $E \rightarrow E + E / E * E / (E) / id.$
   How to answer

   • State grammar E -> E+E / E*E / (E) / id
   • Give first leftmost derivation grouping as id+(id*id)
   • Give second leftmost derivation grouping as (id+id)*id
   • Conclude two distinct parse trees hence ambiguous
6. 7 Marks
   bCan an ambiguous CFG be converted into Chomsky Normal Form. Explain briefly your answer.
   How to answer

   • Define ambiguous CFG and Chomsky Normal Form restrictions
   • CNF conversion preserves language but may change derivations
   • Ambiguity is property of grammar not language; conversion possible
   • Conclude yes with brief justification
7. 7 Marks
   aConstruct PDA for the language $L = \{a^n b^{n+m} c^m,$ where $n \geq 0, m \geq 0\}$.
   How to answer

   • Note need |b| = |a|+|c| split as n+m
   • Push a's then b's, pop for b's matching and c's
   • Define PDA states, stack alphabet, transitions
   • Show acceptance by empty stack / final state
8. 7 Marks
   bConstruct the PDA for the following grammar. $X \rightarrow 0X3$ $X \rightarrow 0A3$ $A \rightarrow 1A2$ $A \rightarrow 12$
   How to answer

   • Interpret productions X->0X3, X->0A3, A->1A2, A->12
   • Use standard CFG to PDA construction with stack
   • Define push/pop transitions for variables and terminals
   • Show acceptance trace
9. 7 Marks
   aDesign a TM to accept the string $L = (a, b)^*$, where $N(a) + N(b) = even$.
   How to answer

   • Idea: TM toggles parity while scanning (a,b)*
   • Define states for even/odd count of N(a)+N(b)
   • Give transition table for a,b,blank with moves
   • Accept in even state on blank
10. 7 Marks
    bGive the tuple definition of Turing machine and explain the significance of movement of R/W head.
    How to answer

    • Define 7-tuple (Q, Sigma, Gamma, delta, q0, B, F)
    • Explain components especially transition and R/W head
    • Significance: bidirectional movement gives memory/computation power
    • Contrast with FA/PDA head movement
11. 7 Marks
    aConvert the following Mealy machine to an equivalent Moore machine by the tabular format.

    

    How to answer

    • Note Mealy outputs on transitions vs Moore on states
    • Split states Q0-Q3 by distinct output pairs
    • Construct Moore table with next states and state outputs
    • Draw Moore diagram/table
12. 7 Marks
    bExplain Chomsky hierarchy of grammar with suitable example.
    How to answer

    • State four types Type-0 to Type-3 with grammars
    • Give example language and automaton for each
    • Show inclusion hierarchy
    • Diagram of hierarchy
13. 7 Marks
    aConvert CFG to GNF $A \rightarrow BB / 1$ $B \rightarrow AA / 0$
    How to answer

    • Check CNF then eliminate terminals from long RHS
    • Break RHS longer than 2 and remove unit/epsilon
    • Apply to A->BB/1, B->AA/0
    • Present final GNF productions
14. 7 Marks
    bConstruct the context free grammar equivalent to a regular expression $(01 + 1)^* (00 + 1)$.
    How to answer

    • Build FA/DFA for $(01+1)^*(00+1)$
    • Introduce variable per state
    • Write regular grammar productions for transitions
    • Add terminal productions for final states
15. 14 Marks
    Write short note on: (Any three)

    1. i)2-way Finite Automata
    2. ii)Properties of Regular Grammar
    3. iii)Multi Tape TM
    4. iv)Arden's Theorem
    How to answer

    • Select any three topics
    • Give definition, diagram/model and key properties for each
    • Give example/application
    • Conclude with significance