Back to Other Questions [Of this Course]
👁️ 85 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: 17-18

Time: 180 minutes | Marks: 60.00

View 125 Topic-wise Questions for this Course

Answer any five sets of questions from the followings.

1.

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

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
b) In compiler, ambiguous testing is a very important matter. 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!
6 Marks
c) Does a push down automata have memory? Justify.

Please SUBSCRIBE to view full question

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

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!
6 Marks
c) Convert ε-NFA to DFA based on Question 2(b)

Please SUBSCRIBE to view full question

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

a) Differentiate between Finite State and Turing Machines.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
b) Convert the following NFA to DFA.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
c) How a DFA processes strings?

Please SUBSCRIBE to view full question

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

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 = {we {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 is not context free.

Please SUBSCRIBE to view full question

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

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
6.

a) Prove that the following language is either regular or not. A= { w w w | w ∈ {a, b} * }

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
b) 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!
5 Marks
c) Write the closure properties of regular languages.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 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) Find DFA's which accepts the following languages: (i) Strings over {a, b} ending in aa. (ii) String over {a, b} containing three consecutive a's (that is, contains the substring aaa) (iii) All strings over {a, b} where each string of length 5 contains at least two a's.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
b) Consider the regular expression (a(cd)*b)*. (i) Find a string over {a, b, c, d}^4 which matches the expression. (ii) Find a string over {a, b, c, d}^4 which does not match the expression.

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:38 p.m.
Converted By (Img/PDF to Text): Baishakhi Bir Nov. 19, 2025, 1:56 a.m.
Reviewed By: Obaydul Hasan Nayeem Nov. 19, 2025, 12:06 p.m.
Back to Other Questions [Of this Course]