Practice
The department’s own question bank. Construction exercises are graded exactly: any correct machine passes, and a wrong one gets the shortest string it fails on — with both machines run on it side by side. Prose questions say so rather than pretending to be gradable.
- 8 marks · CO1 · ApplyM1Draw a DFA for the language of strings starting with 'ab' over Σ = {a, b}.
- 8 marks · CO1 · ApplyM1Design a DFSM for L = {w ∈ {0,1}* : w has 001 as a substring}.
- 8 marks · CO1 · ApplyM1Design a DFSM for L = {w ∈ {a,b}* : w contains an odd number of a's and an even number of b's}.
- 8 marks · CO1 · ApplyM1Obtain a DFA accepting strings of a's and b's having an odd number of a's and an odd number of b's.
- 8 marks · CO1 · ApplyM1Obtain a DFA for the language of strings starting and ending with different characters, over Σ = {0, 1}.
- 8 marks · CO1 · ApplyM1Construct a DFA for L = {w ∈ {a,b}* : |w| mod 3 = 0}.
- 8 marks · CO1 · ApplyM1Design a DFA to accept strings of a’s and b’s where L = {w : |w| mod 5 = 0}.
- 8 marks · CO1 · ApplyM1Design a DFA over {a, b} accepting strings that contain 'aba' as a substring.
- 8 marks · CO1 · ApplyM1Design a nondeterministic FSM for L = {w ∈ {a,b}* : w = aba or |w| is even}.
- 8 marks · CO1 · ApplyM1Design an NDFSM for L = {w ∈ {a,b}* : w is an optional a, followed by aa, followed by zero or more b's}.
- 5 marks · CO1 · UnderstandM1Define, with an example each: (i) alphabet, (ii) power of an alphabet, (iii) language.
- 5 marks · CO1 · UnderstandM1Explain the differences between DFAs and NFAs.
- 8 marks · CO1 · ApplyM1Obtain an ε-NFA accepting zero or more a's, followed by zero or more b's, followed by zero or more c's.
- 8 marks · CO1 · ApplyM1Construct a DFA accepting decimal strings whose value is divisible by 3.
- 8 marks · CO1 · ApplyM1Construct a DFA accepting decimal strings whose value is divisible by 5.
- 8 marks · CO1 · ApplyM1Construct a DFA accepting decimal strings whose value is divisible by 4.
- 8 marks · CO1 · ApplyM1Construct a DFA accepting decimal strings whose value is divisible by 2.
- 8 marks · CO1 · ApplyM1Construct a DFA accepting decimal strings whose value is divisible by 6.
- 8 marks · CO1 · ApplyM1Construct a DFA accepting binary strings whose value is divisible by 3.
- 8 marks · CO1 · ApplyM1Construct a DFA accepting binary strings whose value is divisible by 5.
- 8 marks · CO1 · ApplyM1Construct a DFA accepting base-3 strings whose value is divisible by 4.
- 8 marks · CO2 · AnalyseM2Write a regular expression for binary numerals that are multiples of 2.
- 8 marks · CO2 · AnalyseM2Write a regular expression for strings of a's and b's containing consecutive a's.
- 8 marks · CO2 · AnalyseM2Write a regular expression for strings of a's and b's having odd length.
- 8 marks · CO2 · AnalyseM2Write a regular expression for strings of a’s and b’s whose third symbol from the right is a and fourth from the right is b.
- 8 marks · CO2 · AnalyseM2Design an NDFSM accepting the language of aa*(a+b).
- 8 marks · CO2 · AnalyseM2Design an NDFSM accepting the language of (0+1)*(00+11).
- 8 marks · CO2 · AnalyseM2Obtain an ε-NFA for the regular expression (aa)*(bb)*b.
- 8 marks · CO2 · AnalyseM2Obtain an ε-NFA for the regular expression (0+1)*(00+11)(0+1)*.
- 8 marks · CO2 · AnalyseM2Obtain a regular expression for L = {w ∈ (a+b)* : |w| mod 3 = 0}.
- 8 marks · CO2 · AnalyseM2Show that the regular languages are closed under (a) union, (b) concatenation, (c) star closure and (d) intersection.
- 8 marks · CO2 · AnalyseM2Prove that L = {aⁿbⁿ | n ≥ 0} is not regular.
- 8 marks · CO2 · AnalyseM2Prove that L = {0ⁿ1ᵐ | n ≤ m} is not regular.
- 8 marks · CO2 · AnalyseM2Prove that L = {0ⁿ | n is prime} is not regular.
- 8 marks · CO2 · AnalyseM2State and prove the pumping theorem for regular languages, and prove that L = {wwᴿ | w ∈ {a,b}*} is not regular.
- 8 marks · CO3 · AnalyseM3What is a context-free grammar? Explain a CFG with an example.
- 8 marks · CO3 · AnalyseM3Obtain a CFG generating strings of a’s and b’s where L = {w : |w| mod 3 = 0}.
- 8 marks · CO3 · AnalyseM3For E → E+E | E*E | (E) | id, construct the LMD, RMD and parse tree for (id+id*id).
- 8 marks · CO3 · AnalyseM3Check whether the grammar S → aSb | SS | ε is ambiguous.
- 8 marks · CO3 · AnalyseM3For G with E → E+E | E*E | (E) | id over the input a + b * c, prove the grammar is ambiguous.
- 6 marks · CO3 · AnalyseM3Define left recursion. Eliminate left recursion from: E → E+T | T, T → T*F | F, F → (E) | id.
- 8 marks · CO3 · AnalyseM3Define a PDA. Design a PDA accepting L = {aⁿbⁿ : n ≥ 0}, draw its transition diagram, and show the IDs for aaabbb.
- 8 marks · CO3 · AnalyseM3Construct a PDA accepting L = {wcwᴿ : w ∈ {a,b}*}, and show its moves on "aabcbaa".
- 6 marks · CO3 · AnalyseM3Construct a PDA for the CFG S → 0BB, B → 0S | 1S | 0, and test whether 010000 is accepted.
- 8 marks · CO3 · AnalyseM3Explain the equivalence of PDAs and CFGs with a proper example.
- 6 marks · CO4 · AnalyseM4Eliminate ε-, unit and useless productions from S → aA | aBB, A → aAA | ε, B → bB | bbC, C → B, and convert to CNF.
- 8 marks · CO4 · AnalyseM4Convert to CNF: S → aACa, A → AB | a, B → BC | c, C → CCc | ε.
- 5 marks · CO4 · AnalyseM4Determine whether L = {0ⁿ1ⁿ2ⁿ | n ≥ 1} is context-free.
- 6 marks · CO4 · AnalyseM4Show that L = {ww | w ∈ {0,1}*} is not context-free.
- 6 marks · CO4 · AnalyseM4Show that CFLs are closed under union, concatenation, star, homomorphism and reversal.
- 6 marks · CO4 · AnalyseM4Prove that CFLs are not closed under intersection or complementation.
- 8 marks · CO4 · AnalyseM4Prove that if L is a CFL and R is a regular language, then L ∩ R is a CFL.
- 6 marks · CO5 · AnalyseM5Define a Turing machine. With a neat diagram, explain the working of a basic Turing machine.
- 8 marks · CO5 · AnalyseM5Obtain a TM accepting L = {0ⁿ1ⁿ | n ≥ 1}; draw the transition diagram and show the moves on 000111.
- 8 marks · CO5 · AnalyseM5Obtain a TM accepting strings of 0’s and 1’s ending with 011.
- 8 marks · CO5 · AnalyseM5Design a TM accepting all palindromes over {a,b}; show the sequence of IDs for "ababa".
- 8 marks · CO5 · AnalyseM5Briefly explain the techniques for Turing machine construction, and applications of Turing machines.
- 6 marks · CO5 · AnalyseM5What is a multitape Turing machine? Prove that every language accepted by a multitape TM is recursively enumerable.
- 6 marks · CO5 · AnalyseM5Prove that HALT = {(M, w) : the Turing machine M halts on input w} is undecidable.
- 6 marks · CO5 · AnalyseM5Prove that L_d is not recursively enumerable.
- 6 marks · CO5 · AnalyseM5If L and its complement are both recursively enumerable, show that L is recursive.