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

Time: 180 minutes | Marks: 60.00

View 125 Topic-wise Questions for this Course

Answer Any Five (5) Questions From The Following

1.

a) What is Automata Theory? Describe the applications of Finite Automata.

Please SUBSCRIBE to view full question

Topics: Finite State Automata Solution is Coming!
3 Marks
b) Explain the work of lexical analyzer with an on/off switch.

Please SUBSCRIBE to view full question

Topics: Lexical Analyzer Solution is Coming!
2 Marks
c) The Chomsky Hierarchy is a containment hierarchy of classes of formal languages. Describe with suitable figure(s).

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
d) Analyze the terms: Theorems, Lemmas and Corollaries.

Please SUBSCRIBE to view full question

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

a) Describe the basic functionalities of pumping lemma.

Please SUBSCRIBE to view full question

Topics: Pumping Lemma Solution is Coming!
3 Marks
b) Use the pumping lemma to prove that the language is not context free.

Please SUBSCRIBE to view full question

Topics: Pumping Lemma Solution is Coming!
6 Marks
c) Define push down automata with example.

Please SUBSCRIBE to view full question

Topics: Push Down Automata Solution is Coming!
3 Marks
3.

a) Describe Deductive proof. Prove that, if x is the sum of the squares of four positive integers, then

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
b) Briefly explain the configuration of a TM.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
c) Let x be a real number. Then prove that, [x] = [x] if and only if x is an integer.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
2 Marks
d) For all n ≥ 0, prove that

Please SUBSCRIBE to view full question

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

a) Describe with examples: advantages of DFA.

Please SUBSCRIBE to view full question

Topics: Deterministic Finite Automaton (DFA) Solution is Coming!
4 Marks
b) Construct a DFA for the following language: Let, Σ = {0, 1}, 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!
5 Marks
c) 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: Non-deterministic Finite Automaton (NFA) Solution is Coming!
3 Marks
5.

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

Please SUBSCRIBE to view full question

Topics: Non-deterministic Finite Automaton (NFA) Solution is Coming!
4 Marks
b) Describe the Advantages & Caveats for NFA.

Please SUBSCRIBE to view full question

Topics: Non-deterministic Finite Automaton (NFA) Solution is Coming!
3 Marks
c) Convert the NFA from Question 5(a), to DFA. Question 5(a): Build an NFA for the following language: L = {w | w ends in 101}

Please SUBSCRIBE to view full question

Topics: Deterministic Finite Automaton (DFA) , NFA to DFA or DFA to NFA Solution is Coming!
5 Marks
6.

a) Describe the necessities of explicit ε-transitions in finite automata.

Please SUBSCRIBE to view full question

Topics: Finite State Automata Solution is Coming!
2 Marks
b) Build an e-NFA for the following language: L= ={w|w is empty, or if non-empty will end in 11}

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 e-NFA for the following language: L= ={w|w is empty, or if non-empty will end in 11}

Please SUBSCRIBE to view full question

Topics: NFA to DFA or DFA to NFA Solution is Coming!
6 Marks
7.

a) What is regular expression? Describe the operations of regular expressions.

Please SUBSCRIBE to view full question

Topics: Regular Expressions Solution is Coming!
3 Marks
b) Prove that if L=L(A) for some DFA A, then there is a regular expression R such that L=L(R).

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
c) Convert the following DFA to an equivalent regular Expression.

Please SUBSCRIBE to view full question

Topics: Regular Expressions Solution is Coming!
3 Marks
d) Define- i) Associativity ii) Identity and iii) Distributive Law

Please SUBSCRIBE to view full question

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

a) Regarding conversion of DFA from NFA, a bad case for the Subset Construction is occurred. Analyze this using the Pigeonhole Principle.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
6 Marks
b) Briefly describe, how we can eliminate ε- transitions?

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
c) What are the uses of ε-Transitions?

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:39 p.m.
Converted By (Img/PDF to Text): Baishakhi Bir Nov. 18, 2025, 11:54 p.m.
Reviewed By: Obaydul Hasan Nayeem Nov. 19, 2025, 10:52 a.m.
Back to Other Questions [Of this Course]