Theory of Computing
SWE · Midterm · Spring 24
Section All (FBR)
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 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) Let the alphabet Sigma be the standard 26 letters {a,b,c,d,...z}. If A = {good, bad} and B = {boy, girl}, then find out A U B (union) and A.B (concatenation) | [Marks-2] | CLO-1 Level-4
1. b) i. Design state diagram of Deterministic finite Automata for language L of binary symbol. L = {w | w is the empty string epsilon or ends in a 0} | [Marks-3+2] | CLO-1 Level-4
1. b) ii. Design DFA where L = {w | w is 111 for binary input}.
1. c) Demonstrate the following DFA and show epsilon acceptance. | [Marks-2+1] | CLO-1 Level-4
[Figure: A DFA diagram with states q0, q1, and q2, with transitions labeled a, b, and a,b]
2. a) Contrast the cases where using a DFA is more advantageous than using an NFA. | [Marks-3] | CLO-2 Level-4
2. b) Apply subset construction method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA). | [Marks-4] | CLO-2 Level-4
[Figure: An NFA state diagram with states q0, q1, q2, q3 and transitions labeled 0, 1, epsilon]
2. c) Design 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-3 Level-3
3. a) List 4 applications of Regular expression. | [Marks-2] | CLO-3 Level-3
3. b) Construct Regular Expression for the following Language: L = {w | w starts with b and length is even {b,c}} | [Marks-3] | CLO-3 Level-3