Skip to content

Theory of Computing

SWE · Midterm · Summer 25

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

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