Scribd
Upload
16 views2 pages

Automata Theory Exam Questions 2022

The document outlines the examination paper for Automata Theory and Computability for the Fifth Semester BE Programme, scheduled for Feb/Mar 2022. It consists of ten questions divided into five modules, covering topics such as DFA, NFA, context-free grammar, Turing machines, and decidability. Students are required to answer any four questions for a total of 100 marks.

Uploaded by

BasanGouda Kallur
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views2 pages

Automata Theory Exam Questions 2022

The document outlines the examination paper for Automata Theory and Computability for the Fifth Semester BE Programme, scheduled for Feb/Mar 2022. It consists of ten questions divided into five modules, covering topics such as DFA, NFA, context-free grammar, Turing machines, and decidability. Students are required to answer any four questions for a total of 100 marks.

Uploaded by

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

USN 18CS531/IS531

QP Code: C
Fifth Semester BE Programme Examination Feb/Mar-2022
AUTOMATA THEORY AND COMPUTABILITY

Time: 3Hrs Max. Marks: 100


Note: .Out of 10 Questions students should answer any four questions (total 25x4=100 marks)

SL Marks Course RBT


Module I
No. Outcomes Level

a) Define the following terms: Alphabets, power set,


strings, kleenclouser and concatenation
1. 25 (Marks) CO1 L6
b) Draw the DFA to accept the string of a’s and b’s
having substring aab

Obtain the DFA for the fooling NFA by using Lazy


evaluation method
2. 25 (Marks) CO1 L1,L5
qo a q1 b q2

Module II

a) Construct an NFA for the regular expression 25 (Marks) CO3 L1


(a+b)* aa (a+b).
3.
b) state and prove the pumping lemma theorem for the
regular language and show that L= { WWR | W € (a+b) * }
is not reguar

List out the various closure properties of regular


4. 25 (Marks) CO2 L6
languages and prove that regular languages are closure
under complementation and intersection
Module III
Define the Context free grammar? Construct the CFG
to generate the following language,
5. 25 (Marks) CO3 L1
i) L= { W | na(w) = nb(w) | n>= 1 }
ii) L= { an bn over the ∑=(a,b) | n>= 1 }

What is PDA? Construct PDA which accept een


6. palindrome of the form L={ WCW R | W = (a=b)* } 25 (Marks) CO3 L6
and also show the moves made by the PDA.
18CS5131

Module IV

a) Explain the Working Model of Turing machine with


block diagram.
7. b) Design the Turing machine that accepts the 25 (Marks) CO4 L2,L6
language L={ 0n 1n 2n | n>= 1 } also show the moves
made by the machine for the string 000011112222

a) Explain the multi tape Turing machine with block


8. diagram. 25 (Marks) CO6 L6
b) Explain the mode of Linear Bound Automata

Module V

a) Explain the Hating problem of Turing machine L6


9. 25 (Marks) CO5
b) explain the Post Correspondence Problem

Write a short note on :


a) Decidability
10. b) Un decidable language 25 (Marks) CO2 L4
c) Class of P and NP
d) Quantum Computers

You might also like