Skip to content

Theory of Computing

SWE · Midterm · Spring 26

Paper 2 of 2Section A-JSwitch

Section A-J

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, Spring 2026 Course Code: SE234; Course Title: Theory of Computing Sections & Teachers: FJT(A-D), TM(E), FBR (F-J) Time: 1 Hour 30 Mins | 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) | Draw both a DFA and an NFA for the given language L = {w ∈ {0,1} | w contains substring "10"} and Illustrate how non determinism in an NFA can reduce the number of states compared to an equivalent DFA by constructing both machines for a simple language. | [Marks: 3] | CLO-1 Level-3 1. b) | Construct state diagram of Deterministic finite Automata for language i) L = {w | w starts with 'a' and contains substring "bb" where input is {a,b}} ii) L = {w ∈ {0,1} | number of 0's is divisible by 3} | [Marks: 4] | 1. c) | Demonstrate and identify the following Finite Automata and show epsilon acceptation and 0110101 string acceptance. [Figure: A finite automaton diagram with states q0, q1, q2, q3, transition arrows, and labels] | [Marks: 3] | 2. a) | Illustrate the advantages and disadvantages of Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) in terms of implementation, design, state complexity, memory usage. | [Marks: 3] | CLO-2 Level-3 2. b) | Apply subset construction method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)- [Figure: An NFA transition diagram with states q0, q1, q2 and transitions labeled a, b, a,b] | [Marks: 4] | 2. c) | Construct a Non deterministic finite automata where L = {w| w strings having 3rd symbol 'a' from right end where Σ = {a,b,c}} | [Marks: 3] | 3. a) | Express Regular Expression for the following Language: L = {w| w where each string should have three consecutive b's for input {b,c}} How regular expressions represent patterns in formal languages and evaluate their effectiveness by constructing one example and explaining how it captures the structure of the language? | [Marks: 5] | CLO-3 Level-3