Skip to content

Theory of Computation

CSE · Quiz · Fall 24

Section 64 H

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.

Fall 2024 CSE228 – Theory of Computation Quiz-1 Section: 64_H Time: 30 Minutes Q1. Draw a DFA for the following language defined over Σ = {0,1} [2.5] L = {w | w contains either 010 or 101 as substrings} Q2. Draw a NFA for the following language defined over Σ = {0,1} [2.5] L = {w | w begins or ends with 00 or 11} Q3. Convert the following NFA to equivalent DFA [10] [Figure: A NFA state diagram with states q0, q1, q2, where q0 has a transition on b to q1 and on epsilon to q2, q1 has a self-loop on a and transition on a,b to q2, and q2 has a transition on a to q0.] Daffodil International University Computer Science & Engineering Theory of Computation Time: 30 minutes Marks: 15 Quiz 1 1. Construct a DFA that accepts strings over {a, b} that contain exactly two 'a's. 2. Create an NFA that accepts strings over {0, 1} that can have either the pattern "00" or "11" anywhere in the string. 3. Convert the following NFA to DFA [Figure: An NFA state diagram with states 0, 1, 2, 3, 4 with various transitions involving a, b and epsilon.] Quiz - 01 Course Code: CSE228 Course Title: Theory of Computation Full marks: 15 Time: 40 Minutes Answer each of the following questions 1. a) What is theory of computation, and what are its primary goals in computer science and mathematics? [1+2] 1. b) Suppose two languages L1 = {a, ab, bb} and L2 = {aa, b}. Perform intersection, and concatenation operation on the languages. 2. a) Let M be the Deterministic Finite Automata (DFA) shown below [3+3] [Figure: DFA state diagram with states q0, q1, q2] Provide a formal description of M. 2. b) Construct deterministic finite automata to recognize odd number of 1's and even number of 0's? 3. a) Construct an NFA accepting binary strings with three consecutive 0's. [2+4] 3. b) Convert the epsilon - NFA into its equivalent DFA. [Figure: An epsilon-NFA state diagram with states q0, q1, q2, q3, q4]