Skip to content

Theory of Computing

SWE · Midterm · Fall 23

Section All

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

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]