Skip to content

Theory of Computing

SWE · Midterm · Spring 25

Paper 2 of 2By Sabbir HRSwitch

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 2025 Course Code: SE234 ; Course Title: Theory of Computing Sections & Teachers: FBR (A,B,C,D), FJT (E, F, G, H) , RJM (I) 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) Identify the difference between epsilon and phi with a finite automata diagram. Compare and contrast the advantages and disadvantages of Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) in terms of implementation and design. | [Marks-3] | CLO-1 Level-3 b) Construct Deterministic finite Automata for following language: i) {w | every odd position of w is a 1 for binary alphabet} ii) Let Sigma = {a, b} and let L = {ababa}. Design a DFA for L | [Marks-4] c) Demonstrate the following finite automata and identify it. Also show epsilon/ empty string acceptance for provided finite automata. | [Marks-3] | [Figure: A finite automata diagram with states S0, S1, and S2, transitions with 0 and 1] 2. a) Use formal definition to precisely identify the following automata, and demonstrate computation for the string "0000.". | [Marks-3] | CLO-2 Level-3 | [Figure: NFA diagram with states q0, q1, q2 and transitions 0, 1] b) Apply “Subset construction” method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)- | [Marks-4] | [Figure: NFA diagram for subset construction] c) Sketch a non-deterministic finite automata which accept a string containing “the” anywhere in a string of {a-z}, e.g., “there” but not “those” | [Marks-3] 3. a) Mention real life applications of Regular expression | [Marks-2] | CLO-3 Level-3 b) Construct Regular Expression for the following Language: L= {w| w does contain 3 consecutive b’s where alphabet in {b, d}} | [Marks-3]