MU Computer Engineering (Semester 4)
Theoretical Computer Science
May 2014
Total marks: --
Total time: --
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1(a) Differentiate between NFA and DFA.
5 M
1(b) Explain CNF and GNF with example.
5 M
1(c) state and prove closure properties of context free languages.
5 M
1(d) Give Applications of Regular Expression and finite Automata
5 M

2(a) Construct an NFA with epsilon transition for following RE.
5 M
2(b) Give formal definition of regular expression.Give R>E for following:
Set of all strings over {1,0}that end with and has no substring 00.
Set of all strings over {1,0}with even number of 1's followed by odd number of 0's
5 M
2(c) Compare and Construct Moore and Melay Machine.Construct Moore Machine to find out the residue-modulo-3 for binary numbers.
10 M

3(a) Consider the following grammar:
S\(\rightarrow\)I C t S |I C t S e S|a
For the string 'ibtibtaen find the following:
i)Leftmost derivation
ii)Rightmost derivation
iii)Parse tree
iv)Check if the above grammar is Ambiguous.
10 M
3(b) Design PDA that checks for well-formed parentheses.
10 M

4(a) Design a TM that recognizes palindrome strings where \(\sum\)={0,1}
10 M
4(b) Construct NFA that accept a set of all strings over {a,b}ending with "abb"Covert this NFA to Equivalent DFA.
10 M

5(a) Convert the following Grammar to CNF form:
S\(\rightarrow\) ABA
A\(\rightarrow\)aA|bA| \(\epsilon\)
B\(\rightarrow\) bB|aA|\(\epsilon\)
10 M
5(b) Give and explain the formal statement of pumping lemma for languages and use it to prove that the following languages is not regular:
10 M

Write short notes on:
6(a) Chomsky Hierarchy of Grammar
5 M
6(b) Variants of Turning machine
5 M
6(c) Rice's Theorem
5 M
6(d) Recursive and Recursively enumerable languages.
5 M

More question papers from Theoretical Computer Science