Theory of Computing
SWE · Midterm · Fall 23
Section All
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Department of Software Engineering
Faculty of Science & Information Technology
Midterm Examination, Fall 2023
Course Code: SE234 ; Course Title: Theory of Computing
Sections & Teachers: All & FBR
Time: 1 Hour 30 Mins Marks: 25
Answer ALL Questions
[The figures in the right margin indicate the full marks and corresponding course outcomes. All portions of each question must be answered sequentially.]
1. a) Identify the system in the following case. Are they finite or context free?
a) Automated ticket booking system
b) Automated Door
c) Self driving Car
d) ChatGPT
[Marks-2]
b) Let Σ = {a, b} and let L = { w ∈ Σ* | w ≠ ε and the first and last character of w are the same }. Design a DFA for L.
[Marks-3]
c) Find out the Language for the following finite automata and make it minimal DFA.
[Figure: A finite automata diagram with states A, B, C, D, E, F where A is the start state and D is the accept state]
[Marks-3]
d) Explain why not all NFAs are DFAs yet all DFAs are NFA.
[Marks-2]
2. a) Outline the benefits and drawbacks of DFA and NFA in terms of implementation and design.
[Marks-3]
b) Apply “Subset construction” method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)- Q= {q0, q1, q2. q3, q4}
[Figure: An NFA transition diagram with states q0, q1, q2, q3, q4]
[Marks-4]
c) Construct an NFA with ∑ = {0, 1} in which contain double '1' is followed by double '0'.
[Marks-3]
3. a) Explain Regular Expression for “Password Validation”.
[Marks-2]
b) Construct Regular Expression for the language of all strings over {a, b} such that the as and bs are strictly alternating.
Examples of strings in the language: ε, a, b, ab, ba, aba, bab, abab, baba
Examples of strings not in the language: bb, aa, abba
[Marks-3]