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

University of Barishal

Department of Computer Science and Engineering

Final Exam

Course Title: Theory of Computation (CSE-3203)

Semester: 6th | Session: 16-17

Time: 180 minutes | Marks: 60.00

View 125 Topic-wise Questions for this Course

Answer any Five (5) Questions from the followings.

1.

a) Analyze the terms: Theorems, Lemmas and Corollaries.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
b) What is Automata Theory? Describe the applications of Finite Automata.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
c) A containment hierarchy of classes of formal languages has been classified as The Chomsky Hierarchy. Describe with suitable figure(s).

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
2.

a) Define push down automata with example.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
b) 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!
5 Marks
c) 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!
4 Marks
3.

a) What is Turing Machine? Give advantages of it.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
b) Construct a Turing Machine that accepts the language of palindromes over {a,b}. Also specify the moves to trace the strings abaa, abba,aabaa.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
c) What is meant by a halting problem in a Turing Machine? Explain with an example.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
4.

a) Let, Σ = {0, 1} Construct a DFA for the following language: L = {w | w is a binary string that has even number of 1s and even number of 0s}

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
b) Construct a NFA for the following: Strings where the first symbol is present somewhere later on at least once.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
5.

a) Build an NFA for the following language: L = { w | w ends in 01}

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
b) Describe the Advantages & Caveats for NFA.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
c) Convert the NFA from Question 5(a), to DFA.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
5 Marks
6.

a) Why explicit ε-transitions in finite automata is important?

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
2 Marks
b) Build an ε-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: N/A Solution is Coming!
4 Marks
c) Convert ε-NFA to DFA based on Question 6(b) Question - 6(b): Build an ε-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: N/A Solution is Coming!
6 Marks
7.

a) Describe the relation between Regular Expressions (RE) and Finite Automata. Show with figure that they are interchangeable.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
b) Convert the following RE to ε-NFA: (0+1)*01(0+1)*

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
8.

a) Construct a context-free grammar for the following DFA:

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
b) Show that the grammar ({S}, {a, b}, R, S) with rules R = S -> aS | aSbS | € is ambiguous.

Please SUBSCRIBE to view full question

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

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
2 Marks

--------------------------***-----------------------------

View 125 Topic-wise Questions for this Course

Contributors of this Question:

Role Name Date
Uploaded By: Onebyzero Edu (Test User) July 30, 2024, 6:37 p.m.
Converted By (Img/PDF to Text): Baishakhi Bir Nov. 19, 2025, 11:44 a.m.
Reviewed By: Obaydul Hasan Nayeem Nov. 19, 2025, 5:26 p.m.
Back to Other Questions [Of this Course]