Theory of Computing
SWE · Midterm · Summer 25
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Faculty of Science & Information Technology
Department of Software Engineering
Midterm Examination, Summer 2025
Course Code: SE234 ; Course Title: Theory of Computing
Sections & Teachers: FBR (A-D), FJT (E-H), NJN (I-J), ZNM (K-L), MMN (M), AMR (N)
Time: 1:30 Hrs Marks: 25
Answer ALL Questions
[The figures in the right margin indicate the full marks and corresponding course outcomes. All portions of each question must be answered sequentially.]
1. a) Relate the type of system context free or Finite, applicable for each example:
i) Spell checker in a text editor
ii) Traffic Signal Controller
iii) Simple Vending Machine
iv) Chatbot
[Marks-2] CLO-1 Level-3
b) Construct DFA for the following Languages:
L = {w|w where each string starts and ends with the same symbol and length at least 2}.
[Marks-3]
c) Illustrate the differences between DFA and NFA in terms of:
- State complexity
- Transition rules
- Suitability of Software implementation
[Marks-2]
d) Demonstrate the following finite automata and show string acceptance for string 100110.
[Figure: Finite automaton with states q0, q1, q2, q3]
[Marks-3]
2. a) Construct a non-deterministic finite automata for the following language of input = {a,b} that accepts all strings where every 'a' is followed by at least two 'b'.
[Marks-3] CLO-2 Level-3
b) Apply Subset-construction method to convert the following non-deterministic finite automata to deterministic finite automata-S
[Figure: NFA with states q0, q1, q2, q3, q4 and transitions on a, b]
[Marks-4]
c) Explain with formal argument:
Why is non-determinism considered a theoretical advantage but not a practical one when designing machines?
[Marks-3]
3. a) Construct a Regular Expression for the following Regular Language:
{w | w contains single 1 for Binary input}
Also mention four applications of regular expression.
[Marks-5] CLO-3 Level-3