Hall Ticket No Question Paper Code: AIT002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
B.Tech II Semester End Examinations (Regular/Supplementary) May, 2018
Regulation: IARE R16
THEORY OF COMPUTATION
Time: 3 Hours (Common to ECE EEE) Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Compare NFA, DFA and Epsilon NFA
Design a DFA to accept allbinary strings whose decimal values are divisible by 4.
2. Convert the following " -NFA to DFA
Table 1
" A b c

q

Design NFA for recognizing C Programming language key words such as else, while, for, if, end,
int, float.
UNIT II
3. Construct the NFA for the regular
Write the regular expression to recognize the valid PAN number
4. Describe the closure properties of Regular Languages
Write the right linear grammar for the regular expression
UNIT III
5. Give the context free grammar for the following language: fanbmcmdn n m 0
Is the following grammar is in CNF? If not convert the following grammar into CNF: E E
T F T T F F F E a
6. Consider the Grammar with the following productions
S AaBC
B bB bAB b
C Cb|b
A aA
Write the leftmost and rightmost derivation and parse tree for the string belongs to the

Page 1 of 2
Minimize the following Context free grammar
S aBa Aa
B abC|D
C aaC|c
E ab|Ab|b
UNIT IV
7. Convert the following grammar to a PDA E E T F T T F F F E a
Compare D{DA and NPDA. Give one example for each
8. Explain the following PDA accepting through empty stack ii) PDA Accepting through final
state
Design a PDA to accept a aL wcwRjw andwR is the reverse of w
UNIT V
9. Define a Turing machine and explain its working principle.
Design a Turing machine that will accept the language L over where L L fanbng

10. Write a note on Multidimensional Turing machines
Define the following with an example: Recursively enumerable languages ii) Recursive languages