STUPIDSID
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.
(00+11)*(10)*
(00+11)*(10)*
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
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
C\(\rightarrow\)b
For the string 'ibtibtaen find the following:
i)Leftmost derivation
ii)Rightmost derivation
iii)Parse tree
iv)Check if the above grammar is Ambiguous.
S\(\rightarrow\)I C t S |I C t S e S|a
C\(\rightarrow\)b
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\)
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:
L={a^{n}b^{n}|n>=1}
L={a^{n}b^{n}|n>=1}
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