Reg No.:

000001T303121901

Pages: 2

Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

Fifth Semester B.Tech Degree Regular and Supplementary Examination December 2020

Max. Marks: 100

b)
0)
6)

0)
௦)

b)
௦)

b)
0)

0)

0)

0)

Course Code: 11303
Course Name: THEORY OF COMPUTATION
PARTA
Answer any two full questions, each carries 15 marks.
Write down the applications of Finite Automata.
Construct a DFA over Z={0,1}that accepts odd number of 0’s.
What is meant by language acceptability in FSA? Explain with an example.
Explain String concatenation with an Example
What is meant by non-determinism? Design an NFA over &={a,b}for the
language L such that L={Set of all strings ends with ’ab’}.
Explain Chomsky classification of grammars with examples.
Differentiate between NFA and DFA.
Explain the concept of Kleene closure.
Explain Transition Diagram and Table.
Design a Mealy machine to print 2’s complement of a binary number.
PART ‏تا‎
‎Answer any two full questions, each carries 15 marks.
State pumping lemma for regular languages.
State and prove Arden’s theorem.
List the major steps followed in State Elimination Method for converting a
finite automata to regular expression.
Prove that the language A={ yy | y €{0,1} * is NOT REGULAR
Define PDA. Explain with an example.

Write regular expression for the language

L={Set of all strings whose length is divisible by 3}
Simplify the following CFL:

5௨%, A> BAd/bSX/a, BD aSB/bBX, X>SBD/aBX/ad
Explain GNF with an example.

Page 1 of 2

Duration: 3 Hours

Marks
(4)
(5)
(4)
(2)
(5)

(6)
(4)
(4)
(6)
(5)

(2)
(8)
(5)

(8)

(7)
(4)

(8)

(3)