Skip to content

Theory of Computing

SWE · Midterm · Spring 24

Section All (FBR)

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 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