Skip to content

Theory of Computing

SWE · Final · Spring 25

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 Faculty of Science & Information Technology Department of Software Engineering Final Examination, Spring 2025 Course Code: SE234; Course Title: Theory of Computing Sections & Teachers: FBR (A,B,C,D), FJT (E, F, G, H), RJM (I) Time: 2:00 Hrs Marks: 40 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) Demonstrate the regular language for the following expression and show one supported and one not supported string: 0* (100*)* [Marks-3] CLO-3 Level-3 b) L1) Discover regular expressions corresponding to the language of the binary alphabet where strings have length at least 4 and its third symbol from the right end will not be 1. L2) Discover a Regular expressions defined over {a, b, c} for Language {E, c} [Marks-5] c) Apply state elimination method to discover the Regular expression from the following DFA [Figure: DFA with states q0, q2, q1, transitions q0 to q0 with 1, q0 to q2 with 0, q2 to q2 with 0, q2 to q1 with 1, q1 to q1 with 0,1] [Marks-5] d) Examine whether the given grammar is ambiguous or not S -> AB / aaB A -> a / Aa B -> b [Marks-3] e) i) Construct context free grammars to accept the following languages. ̳ = {0, 1} {w | w starts and ends with the different symbol} ii) Construct a CFG that generates the language: L(G) = {a^n b^m c^m d^2n | n ≥ 1, m > 2}. [Marks-5] f) Consider the following Context free grammar and evaluate any derivation and parse tree for the string acbd. S -> AB A -> c | aA B -> d | bB [Marks-4] g) Illustrate a Non deterministic finite automata for the following regular expression by using the Lemma method. a*(a+b)*b + ab [Marks-5] h) Construct a Push down Automata for the following language: L = {a^n b^m c^m d^n ; n,m >= 1} [Marks-5] 2. a) Picture a Turing Machine graphically over ̳ = {a,b} for the language, L= {w | where w contains baa} [Marks-2] CLO-4 Level-3 b) Turing machines are theoretical models of computation that can be used to define what problems are computationally decidable. Summarize the initial configuration of the Turing machine by mentioning the operations on the tape. [Marks-3]