Back to Other Questions [Of this Course]
👁️ 190 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: 19-20

Time: 180 minutes | Marks: 60.00

Course Teacher: Dr. Md Manjur Ahmed

View 125 Topic-wise Questions for this Course

(Note: Answer any five set of questions from the followings)

1.

a) Define Turing Machine. Explain pushdown automaton.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
b) Prove that every language accepted by a multitap TM is recursively enumerable.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
c) What do you know about context-free grammars?

Please SUBSCRIBE to view full question

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

a) Define with examples: Alphabet, String, Language

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
b) Give a regular expression for the following language B over the alphabet {a, b}. B={w | w does not contain the substring aaa}.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
c) When is an expression called regular expression?

Please SUBSCRIBE to view full question

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

a) 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!
3 Marks
b) Convert the following NFA to DFA.

Please SUBSCRIBE to view full question

Topics: Deterministic Finite Automaton (DFA) , Non-deterministic Finite Automaton (NFA) Solution is Coming!
6 Marks
c) State the Pumping Lemma for regular languages.

Please SUBSCRIBE to view full question

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

a) Summarize the principal closure properties for regular languages.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
b) Convert DFA's to regular expressions by eliminating states (using an arbitrary example).

Please SUBSCRIBE to view full question

Topics: Deterministic Finite Automaton (DFA) , Regular Expressions Solution is Coming!
5 Marks
c) Prove that if L is a regular language over the following alphabet, then it is also a regular language.

Please SUBSCRIBE to view full question

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

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

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
5 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) Explain inverse homomorphism.

Please SUBSCRIBE to view full question

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

a) Elaborate the three operations on languages that the operations of regular expression represent.

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) Prove that the following are not regular languages: (i) The set of strings of 0's and 1's beginning with 1, such that when interpreted as an integer, that integer is a prime. (ii) The set of strings of the form 0 i1 j such that the greatest common divisor of i and j is 1.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
b) State the properties of a parse tree. Construct a parse tree for the following string: S --> S S + | S S * l a

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
c) Prove that every language defined by a regular expression is also defined by a finite automata.

Please SUBSCRIBE to view full question

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

a) State formal definition of a finite automata. Give an example.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 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) Build an e-NFA for the following language: [The question is incomplete]

Please SUBSCRIBE to view full question

Topics: N/A 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: Subrina Jahan Meem Oct. 27, 2024, 6:27 p.m.
Converted By (Img/PDF to Text): Obaydul Hasan Nayeem Nov. 18, 2025, 7:46 p.m.
Reviewed By: Obaydul Hasan Nayeem Nov. 18, 2025, 8:13 p.m.
Back to Other Questions [Of this Course]