Scribd
Upload
1K views3 pages

Question Paper: Bms College of Engineering

1) The document is a question paper for an exam on Theoretical Foundations of Computations. It contains 7 questions worth a total of 100 marks to be completed within 210 minutes. 2) The questions cover topics like constructing DFAs and regular expressions, using pumping lemma to show languages are not regular, constructing NFAs and PDAs, obtaining grammars, and designing Turing machines. 3) The document provides internal choices for some questions for students to choose between related problems. It also instructs students to answer all questions and that missing data may be assumed if needed.

Uploaded by

cool
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1K views3 pages

Question Paper: Bms College of Engineering

1) The document is a question paper for an exam on Theoretical Foundations of Computations. It contains 7 questions worth a total of 100 marks to be completed within 210 minutes. 2) The questions cover topics like constructing DFAs and regular expressions, using pumping lemma to show languages are not regular, constructing NFAs and PDAs, obtaining grammars, and designing Turing machines. 3) The document provides internal choices for some questions for students to choose between related problems. It also instructs students to answer all questions and that missing data may be assumed if needed.

Uploaded by

cool
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Question Paper

Exam Date & Time: 15-Oct-2020 (09:30 AM - 01:00 PM)

BMS COLLEGE OF ENGINEERING

Autonomous Institute Affiliated to VTU, Supplementary Semester End Examinations October 2020
Theoretical foundations of Computations [19CS4PCTFC]
Marks: 100 Duration: 210 mins.

Branch: CSE - Semester IV


Answer all the questions.
Instructions: 1. Answer FIVE full questions, using the given internal choices. 2. Missing data, if any, may be suitably assumed.

1) (10)
Construct a DFA to accept a string w satisfying the following condition:
a) |w| mod 3 >=|w| mod 2 where w ∈ Σ* and Σ={a}

b) (10)

2) (5)
Obtain regular expression to accept the strings of a's and b's such that every block of four
a) consecutive symbols consists of at least two b's.

b) Using Pumping Lemma, show that the language L = {an! | n>=0 } is not regular. (6)

c) (9)

[OR] Obtain an NFA for the regular expression (a+b)*aa(a+b)*. Show the step by step procedure involved (10)
3) in constructing the NFA.
Page #1
a)
b) (10)

4) Obtain a grammar to generate a language consisting of all non-palindromes over {a,b}. Give the (6)
derivation for the string abbaba which is not a palindrome.
a)
b) (6)

c) (8)

[OR] (10)
5)

a)

b) (10)

6) Obtain the PDA to accept the language L = { WW R | W∈ (a + b)* }. (10)

a)
b) (10)

Page #2
7) Obtain a Turing Machine which accepts all strings that begin and end with the same symbol over (10)
{0,1}.
a)
b) Explain the following: (10)
i. a language that is not recursively enumerable
ii. undecidable problems that are RE

-----End-----

Page #3

You might also like