Theory of Computing
SWE · Midterm · Fall 24
Section All
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}