STUPIDSID
1 (a)
Define a Regular Expression with the help of an example. Briefly discuss the applications of Regular Expressions.
5 M
1 (b)
Explain with an example the Chomsky Normal form.
5 M
1 (c)
Compare and contrast DPDA and NDPDA.
5 M
1 (d)
Design a FSM that checks if a given decimal number is even.
5 M
2 (a)
Design a Turning Machine to accept strings of type 0n1n, n?1.
10 M
2 (b)
Convert the following grammar to GNF
S?XA/BB
B?b/SB
X?b
A?a
S?XA/BB
B?b/SB
X?b
A?a
10 M
3 (a)
Using pumping lemma checks if anbn is regular, where n?1.
8 M
3 (b)
Design a Turning Machine to find value of log n, where n is a unary number.
12 M
4 (a)
Draw NFA with ? moves that recognizes the RE(a+b)*ab. Convert the above NFA to DFA.
10 M
4 (b)
Design a PDA that accepts all the strings containing equal number of a's and b's.
10 M
5 (a)
What are the steps to convert a MOORE Machine to Mealy Machine. Design a Moore Machine to convert each occurrence of 100 to 101. Convert it into an equivalent Mealy Machine using the above mentioned steps.
10 M
5 (b)
Consider the following grammar.
S?SAS
S?b
A?ba
A?b
For the string "bbabbbbab" derive
i) Left most derivation
ii) Right most derivation
iii) Parse Tree.
S?SAS
S?b
A?ba
A?b
For the string "bbabbbbab" derive
i) Left most derivation
ii) Right most derivation
iii) Parse Tree.
10 M
6 (a)
Design a PDA to check for well-formed parentheses.
10 M
6 (b)
Discuss different classes of Chomsky hierarchy in detail.
10 M
Write short note on any four:
7 (a)
Kleen's Clousure
5 M
7 (b)
Post Correspondence Problem
5 M
7 (c)
Myhill Nerode Theorem
5 M
7 (d)
Halting Problem
5 M
7 (e)
Arden's Theorem
5 M
More question papers from Theory of Computer Science