Sem: V [A,B] Sub: Theory of Computation Code: BCS503
(Year: 2025-2026)
Question Bank: Module-1
1 Define the following terms with suitable examples:
i) Aplhabet ii) Power of an alphabet iii) Concatenation iv) Language
2 Why study the theory of Automata or theory of computation? Explain in brief.
3 List and Explain the Operations on Languages.
4 Design a DFA for the Language L = {w ϵ {a,b}*:w contains even number of a’s and odd
number of b’s}. Show the moves made by the machine on the string: abaabb
5 Design DFA to accept all the strings of a’s and b’s not ending with bab.
Show the sequence of states the machine is in for the string: bababa
Design the DFA for the following Languages:
i) L = { w ϵ {0,1}*: w is a string divisible by 5}
6 ii) Set of all strings such that number 0’s is even and number of 1’s is a multiple of
3 over ∑ = { 0,1}
Construct a DFA for L = { w ϵ { a,b} * : the 4 Symbol from the last is a }.
th
7 Also , show the moves made by the machine on: babaaba
8 Build a DFA to accept strings of 0’s and 1’s that begin and end with the same symbol.
Design the DFA for the following Language over Σ = { a,b}
9 i) Set of all strings ending with ab or ba
ii) Set of all strings not containing the substring:aab
10 Define DFA. Write the difference between DFA, NFA and ∈-NFA
11 Design NFA to accept all the strings of a’s and b’s ending with either ab or ba.
Show the moves made by the NFA on the string: bbaba
12 Define an NFA and Construct an NFA that accepts the language aa*(a|b).
And also ,Convert it to an equivalent DFA using subset Construction method.
13 Define an ε-NFA. Design an ε-NFA for recognizing decimal numbers in standard form.
Convert the ε-NFA given in Fig. to an
equivalent DFA.
14
Consider the following ε-NFA:
δ ε a b
q0 {q2} { q1} {q0,q2}
15 q1 ∅ { q0 } ∅
*q2 {q0,q1} { q2 } { q0 }
i) Compute the ε-closure of each state.
ii) Construct an equivalent DFA using the subset constrcuction Method.