Model Question Paper-1 With Effect From 2019-20 (CBCS Scheme)

18CS54
Model Question Paper-1 with effect from 2019-20 (CBCS Scheme)

USN
Fifth Semester B.E. Degree Examination

AUTOMATA THEORY AND COMPUTABILITY
TIME: 03 Hours Max. Marks: 100
Note: Answer any FIVE full questions, choosing at least ONE question from each MODULE.
Module – 1
Define the following with example. i). Alphabet ii). Power of an alphabet.
(a) 5
iii). Concatenation iv). Language
Define DFSM. Draw a DFSM to accepts
i) decimal strings which are divisible by three.
(b) 10
Q.1 ii) L = {w / w ∈ {a,b}* is the string with even no. of a’s and odd no. of b’s}
iii) L ={w/ w ∈ {a,b}* is the string of a’s and b’s and end with the sub string abb}
(c) With a neat diagram, explain a hierarchy of language classes in Automata Theory 5
OR
Convert the following NDFSM to its equivalent DFSM.
ε a b c
(a)  p {q, r} Φ {q} {r} 8
q Φ {p} {r} {p, q}
*r Φ Φ Φ Φ
(b) Write a note on finite state transducers. 4

Q.2
Minimize the following DFSM.
0 1
→A B A
B A C
(c) C D B 8
*D D A
E D F
F G E
G F G
H G D
Module – 2
(a) Define Regular expression. Write RE for the following Languages 8
i) L = {a 2n b 2m | n>=0, m>=0}
ii) L = {w : |w| mod 3 = 0 where w ∈ {a,b}*}
iii) Language of all strings of 0's and l's that has at least one pair of consecutive 0's
Q.3
(b) State and prove the Pumping Lemma Theorem for Regular languages. 8
Write the Applications of Regular Expressions. 4

(c)
OR
(a) Using Kleen's theorem, prove that any language that can be defined with a Regular 8
Expression can be accepted by some FSM.
(b) Prove that the Regular Languages are Closed Under Complementation and Intersection. 6
18CS54
Q.4 Obtain NDFSM for the Regular expression (a+b)* abb and (a* + ab) aab* 6
(c)
Module – 3
Q.5 (a) Define Context Free Grammer. Write the CFG for the following Languages. 8
i) L={an bn cm: n, m>=0}
ii) L={an bn+2 : n>=0}
iii) L={w ∈ {a,b}*: na(w)=nb(w)}
Define the following with example 6
(b)
i) Leftmost Derivation
ii) Rightmost Derivation
iii) Parse Tree
(c) Define Ambiguous Grammar. Show that following grammar is Ambiguous.
S iCtS | iCtSeS | a 6
C b
OR
Q.6 (a) Discuss Chomsky normal form and Greibach normal form. Convert the following `10
Grammar to Chomsky Normal form.
S  aACa
AB|a
BC|c
C  cC | ε
Define NPDA. Write NPDA for the following languages 10
(b)
i) L = {wcwR | w ∈ { a, b }*}
ii) L={an bn | n>=0}
Module – 4
Q.7 (a) With a neat diagram, explain variants of Turing Machines. 10
Explain Language Acceptability and Design of Turing Machines. 10
(b)
OR
Q.8 (a) Define Turing Machine Model. Explain the representation of Turing Machines. 10
(b) Explain the Model of Linear bound Automation. 10
Module - 5
Q.9 (a) Explain the following with example, 10
i) Decidability ii) Decidable languages iii) Undecidable languages.
(b) Discuss Halting problem and post correspondence problem with respect to TM. 10
OR
Q.10 (a) Write Short notes on 20
i) Growth rate of Function
ii) Classes of P and NP
iii) Quantum Computers
iv) Church Turing Thesis
18CS54
Table showing the Bloom’s Taxonomy Level, Course Outcome and Programme
Outcome
Question Bloom’s Taxonomy Level Course Programme Outcome

attached Outcome
Q.1 (a) L1 CO1 PO1,PO2,PO3,PO4,PO12
(b) L2 CO1 PO1,PO2,PO3,PO4,PO12
(c) L1 CO1 PO1, PO2,PO3,PO4,PO12
Q.2 (a) L3 CO1 PO1, PO2,PO3,PO4,PO12
(b) L1 CO1 PO1, PO2,PO3,PO4,PO12
(c) L3 CO1 PO1, PO2, PO3, PO4, PO12
(b) L1 CO2 PO1,PO2,PO3,PO4,PO12
(c) L1 CO2 PO1, PO2,PO3,PO4,PO12
Q.4 (a) L1 CO2 PO1, PO2, PO3, PO4, PO12
(b) L1 CO2 PO1, PO2,PO3,PO4,PO12
(c) L2 CO2 PO1, PO2, PO3, PO4, PO12
(b) L1 CO3 PO1, PO2, PO3, PO4, PO12
(c) L3 CO3 PO1, PO2,PO3,PO4, PO12
Q.6 (a) L3 CO3 PO1, PO2, PO3, PO4
(b) L2 CO3 PO1, PO2, PO3, PO4
Q.7 (a) L2 CO4 PO1, PO2, PO3, PO4
(b) L2 CO4 PO1, PO2, PO3 , PO4
Q.8 (a) L2 CO4 PO1, PO2, PO3, PO4
Q.9 (a) L2 CO5 PO1, PO2, PO3, PO4
Q.10 (a) L1 CO5 PO1, PO2, PO3, PO4
Lower order thinking skills

Bloom’s Remembering( Understanding Applying (Application):
Taxonomy knowledge):𝐿1 Comprehension): 𝐿2 𝐿3
Levels Higher order thinking skills
Analyzing (Analysis): 𝐿4 Valuating (Evaluation): 𝐿5 Creating (Synthesis): 𝐿6

Model Question Paper-1 With Effect From 2019-20 (CBCS Scheme)

Uploaded by

Copyright:

Available Formats

Model Question Paper-1 With Effect From 2019-20 (CBCS Scheme)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Model Question Paper-1 With Effect From 2019-20 (CBCS Scheme)

Uploaded by

Copyright:

Available Formats

18CS54

Model Question Paper-1 with effect from 2019-20 (CBCS Scheme)

Fifth Semester B.E. Degree Examination

Convert the following NDFSM to its equivalent DFSM.

(b) Write a note on finite state transducers. 4

Write the Applications of Regular Expressions. 4

Question Bloom’s Taxonomy Level Course Programme Outcome

Lower order thinking skills

You might also like