Skip to content

Theory of Computing

SWE · Final · Spring 26

Paper 1 of 3By Sabbir HRSwitch

Paper 1 of 3

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 2026 Course Code: SE234; Course Title: Theory of Computing Sections & Teachers: FJT(A-D), TM(E), FBR (F-J) 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+1)(0+1)*1(0+1)(0+1) [Marks-3] CLO-3 Level-3 b) Discover Regular Expression for the following languages over {0,1} i. L={w|w starts with 0 and has odd length or ends with 1 and has even length} ii. L={w|w has exactly one occurrence of 0} [Marks-5] c) Apply state elimination method to discover the Regular expression from the following DFA [Figure: A DFA with states q0, q1, and q2. State q0 has a transition to q1 on 'a' and to q2 on 'b'. State q1 has a self-loop on 'a,b'. State q2 has a self-loop on 'a,b'.] [Marks-5] d) Construct context free grammars to accept the following languages. i) L={w|w is a binary string such that the number of 0's in w is divisible by 3} ii) L={w|w is a odd length palindrome over the alphabet {x,y}} [Marks-5] e) S -> aB | bA A -> a | aS | bAA B -> b | bS | aBB [Marks-5] i. Construct a Parse tree by showing LMD for the string aabbabba following the above CFG grammar. ii. Prove that the grammar is ambiguous or not? f) Illustrate a Non deterministic finite automata for the following regular expression by using the Lemma method. ((a+b)(c+d)*) + (a*bc*) [Marks-5] g) Context-free grammar for the Language L S->AB A->aAb | ab B->CBd | cd Construct a Pushdown Automaton (PDA) that recognizes the language L. Specify the transition functions of the PDA. Demonstrate how the PDA processes the input string aaabbbccdd, showing the sequence of transitions including stack operation. [Marks-7] 2. a) Picture a Turing Machine graphically over Sigma={a,b} for the language, L= {a^n b^n | n>=1} [Marks-3] CLO-4 Level-3 b) Turing machines are abstract computational models used to determine which problems can be solved algorithmically Describe the working principle of a Turing machine in detail, including its components and step-by-step execution process. [Marks-2]