Skip to content

Theory of Computation

CSE · Final · Fall 24

Paper 2 of 2Batch 64 · Robiul Karim JesanSwitch

Batch 64

Paper 2 of 2

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 Computer Science & Engineering Final Examination, Fall 2024 Course Code: CSE228, Course Title: Theory of Computation Level: L2 Term: T2 Batch: 64 Time: 02: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.] Q1(a) Consider the following CFG: P -> ABCD A -> aA | cC | oD | iC B -> ov | ovC C -> id | id-D | e D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Experiment the above CFG to find out if the above mentioned CFG is ambiguous or not for the string covid-19. Marks: [3] | CO2 Q1(b) Apply the concept of Push Down Automata (PDA) to accepts the language over alphabet {0,1,c}: L = { wcw^R, where w^R is the reverse of w and w in {0+1}* }. After designing the PDA, Experiment the validity of the string 10011c11001 Marks: [7] | CO2 Q2(a) Consider the following CFG: S -> O S S | A, O -> + | * | /, A -> a | b | c Analyze this CFG for the string + a * b /ca to Perform the Left most derivation, Right most derivation, also Generate Parse Tree Marks: [5] | CO3 Q2(b) Drive the following regular expression into CFG: 0*10(0+1)* Using the generated CFG: Discover whether the strings 101001, and 011010, are accepted or not accepted. Marks: [5] | CO3 Q3 Consider the following grammar: S -> ASB A -> aASAB | a | c B -> SbS | A | bb Perform the following steps: i) Eliminate useless symbols from the grammar. ii) Remove unit productions from the grammar. iii) Eliminate epsilon (e)-productions from the grammar. iv) Convert the resulting grammar into Chomsky Normal Form (CNF). Marks: [10] | CO3 Q4(a) Propose the Pumping Lemma for the language A = {a^j b^j | j>=0} is not regular. Marks: [5] | CO4 Q4(b) Determine a Turing Machine which recognizes the languages L = { a^n b^2n | n>= 1 } Marks: [5] | CO4