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