Back to Other Questions [Of this Course]
👁️ 65 views
University of Barishal Logo

University of Barishal

Department of Computer Science and Engineering

1st Mid Exam

Course Title: Theory of Computation (CSE-3203)

Semester: 6th | Session: 20-21

Time: 100 minutes | Marks: 40.00

Course Teacher: Dr. Md Manjur Ahmed

View 125 Topic-wise Questions for this Course

Time: 50+50 Minutes, Marks: 40 (will be converted to 20% marks)

1.

1) Make an NFA: Strings where the first symbol is present somewhere later on at least once.

Please SUBSCRIBE to view full question

Topics: Non-deterministic Finite Automaton (NFA) Solution is Coming!
4 Marks
2) i) Analyze about the "Bad Case for the Subset Construction" during DFA to NFA conversion. ii) Describe the "pigeonhole principle" regarding the subset construction.

Please SUBSCRIBE to view full question

Topics: Deterministic Finite Automaton (DFA) , NFA to DFA or DFA to NFA , Non-deterministic Finite Automaton (NFA) , Pigeonhole Principle Solution is Coming!
8 Marks
3) Build in ε-NFA for the following language: L = {w | w is empty, or if non-empty will end in 01}

Please SUBSCRIBE to view full question

Topics: Epsilon NFA , NFA to DFA or DFA to NFA Solution is Coming!
4 Marks
4) i) Prove that if we add a finite set of strings to a regular language, the result is a regular language. ii) A language L is accepted by some e-NFA if and only if L is accepted by some DFA.

Please SUBSCRIBE to view full question

Topics: Regular Expressions, Regular Grammar and Regular Languages Solution is Coming!
8 Marks
5) Convert the following RE to ε-NFA: (0+1)*01(0+1)*

Please SUBSCRIBE to view full question

Topics: RE to DFA/NFA or DFA/NFA to RE Solution is Coming!
4 Marks
6) i) Prove the theorem "a mod b = b mod a, if and only if a = b. ii) By method of induction, proof the theorem "if x ≥ 4 then 2* ≥ x².

Please SUBSCRIBE to view full question

Topics: Mathematical Induction Solution is Coming!
8 Marks
7) Describe the importance of Automata Theory.

Please SUBSCRIBE to view full question

Topics: Basic Automata Theory Solution is Coming!
4 Marks

................................................................

View 125 Topic-wise Questions for this Course

Contributors of this Question:

Role Name Date
Prepared By (Teacher): Dr. Md Manjur Ahmed N/A
Uploaded By: Sabii Ha Sept. 22, 2025, 7:54 a.m.
Converted By (Img/PDF to Text): Obaydul Hasan Nayeem Nov. 18, 2025, 7:32 p.m.
Reviewed By: Obaydul Hasan Nayeem Nov. 18, 2025, 7:42 p.m.
Back to Other Questions [Of this Course]