👁️ 60 views
University of Barishal Logo

University of Barishal

Department of Computer Science and Engineering

2nd Mid Exam

Course Title: Theory of Computation (CSE-3203)

Semester: 6th | Session: 19-20

Time: 45 minutes | Marks: 50.00

Course Teacher: Dr. Md Manjur Ahmed

Exam Date: October 8, 2025

1.


1) Define push down automata with example.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
5 Marks
2) Give pushdown automata that recognize the following languages: (a) A = { w∈ {0, 1} * | w contains at least three 1s } (b) B = { w∈ {0, 1} * | w = w^R and the length of w is odd }

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
8 Marks
3) Use the pumping lemma to prove that the language A is not context free.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
10 Marks
4) Prove that if we add a finite set of strings to a regular language, the result is a regular language.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
8 Marks
5) Write the closure properties of regular languages.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
5 Marks
6) Does a push down automata have memory? Justify.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks

Contributors of this Question:

Role Name Date
Prepared By (Teacher): Dr. Md Manjur Ahmed Oct. 8, 2025
Uploaded By: Subrina Jahan Meem Oct. 8, 2024, 8:46 p.m.
Converted By (Img/PDF to Text): Obaydul Hasan Nayeem Nov. 18, 2025, 8:15 p.m.
Reviewed By: Obaydul Hasan Nayeem Nov. 18, 2025, 8:21 p.m.