Skip to content

Theory of Computing

SWE · Midterm · Spring 23

Section A

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 Department of Software Engineering Faculty of Science & Information Technology Midterm Examination, Spring 2023 Course Code: SE234 ; Course Title: Theory of Computing Sections & Teachers: A (35 Batch) , A (36 Batch) & FBR 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 ε and phi with finite automata diagram. [Marks-2] [CLO-1, Level-3] b) Construct Deterministic finite Automata for following language: {w | every odd position of w is a 1 for binary alphabet}. II. Let Sigma = {a, b} and let L = {baa}. Design a DFA for L. [Marks-2.5+2.5] [CLO-1, Level-3] c) Demonstrate the following DFA and show epsilon acceptance. [Figure: DFA with states q0, q1, q2 and transitions on a, b] [Marks-3] [CLO-1, Level-3] 2. a) Differentiate DFA and NFA by showing a proper example with diagram. [Marks-3] [CLO-2, Level-5] b) Formulate subset construction method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)- [Figure: NFA with states q0, q1, q2 and transitions] [Marks-4] [CLO-2, Level-5] c) Construct a Non deterministic finite automata for input {a,b} where L = {w | w where any numbers of a's followed by any number of b's}. [Marks-3] [CLO-2, Level-5] 3. a) Explain Regular Expression and compare a* and a+. [Marks-3] [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,c}}. [Marks-2] [CLO-3, Level-3]