Skip to content

Theory of Computing

SWE · Midterm · Fall 24

Section All

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, Fall 2024 Course Code: SE234 ; Course Title: Theory of Computing Sections & Teachers: All & 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 system in the following case. Are they finite or context free? | [Marks-2] | CLO-1 Level-4 a) Automated ticket booking system b) Automated Door c) Self driving Car d) ChatGPT 1. b) Let Sigma = {a, b} and let L = { w in Sigma* | the first and last character of w are not the same }. Construct a DFA for L. | [Marks-3] 1. c) Identify the following finite automata by mentioning the significant difference between determinism and non-determinism. | [Marks-3] | [Figure: A finite automaton state diagram with states q0, q1, q2, q3 and transitions labeled with 0 and 1] 1. d) Choose the method that is best suited for implementation from DFA and NFA, the two approaches to building finite automata, and provide an explanation. | [Marks-2] 2. a) Use formal definition to precisely identify the following automata, and demonstrate computation for the string "0000.". | [Marks-3] | CLO-2 Level-4 [Figure: A finite automaton state diagram with states q0, q1, q2 and transitions] Q = { q0, q1, q2 } 2. b) Apply "Subset construction" method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)- | [Marks-4] | [Figure: An NFA state diagram with states q0, q1, q2 and transitions labeled with 0, 1, 0,1] 2. c) Design a non-deterministic finite automata for the following language of binary input | [Marks-3] L = {w : w contains three consecutive 111} 3. a) Explain Regular Expression with examples . | [Marks-3] | CLO-3 Level-3 3. b) Construct Regular Expression for the language of all strings over {a, b} where: | [Marks-2] L = {epsilon, a, b, aa, ab, ba, bb}