Theory of Computation
CSE · Quiz · Fall 24
Section 64 H
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]