Skip to content

Theory of Computing

SWE · Midterm · Summer 26

Paper 2 of 2By Tonmoy Chandra MudiSwitch

Paper 2 of 2

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 2026 Course Code: SE234 Course Title: Theory of Computing Sections & Teachers: DDK (A-C), KRY (D, N-O), SHN (E-H), AMR (I-L), AAA (M) 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) Model a Deterministic Finite Automaton (DFA) over Sigma={a, b} for the language - | [Marks-5] | CLO-1 L = {w | w starts with ab and ends with ba}. | Level-4 Show both the state diagram and the transition table. 1. b) Diagram a Deterministic Finite Automaton (DFA) over Sigma={0, 1} for the language - | [Marks-3] L = {w | w contains exactly two 1's}. 1. c) [Figure: A DFA state diagram with states q0, q1, q2, q3. q0 has transitions: 'a' to q1, 'b' to q3. q1 has transitions: 'a' to q1, 'b' to q2. q2 has transitions: 'a' to q1, 'b' to q2. q3 has transitions: 'a, b' to q3.] | [Marks-2] Trace the computation of the above DFA for each of the following strings and confirm whether each string is accepted or rejected. i. abbaba ii. abbaaab 2. a) Model a Non-deterministic Finite Automaton (NFA) over Sigma={a, b} for the language | [Marks-3] | CLO-2 L = {w | where every a should be followed by bb}. | Level-4 Show both the state diagram and the transition table. 2. b) Transform the following NFA into an equivalent DFA using the subset construction method. | [Marks-7] [Figure: An NFA state diagram with initial state q0 having an epsilon transition and a loop 'a, b' to q0, and transition 'a' to q1. q1 has transition 'a' to q2. q2 has transition 'b' to q3.] 3. a) Derive a regular expression for the language | [Marks-3] | CLO-3 L = {w | w has an even number of a's}. | Level-3 3. b) Derive a regular expression for the language | [Marks-2] L = {w | w contains any number of a's followed by any number of b's}.