STUPIDSID
1(a)
Define DFA List three household applications of finite Automate.
2 M
1(b)
What is a trap state in FA? State and explain the properties of transition functions.
2 M
1(c)
Design deterministic finite automation accepting the following languages over the alphabet{0,1}:
i)The set of all words ending in 00.
ii)The set of all words exceptε
iii) The set of all words that begin with 0.
i)The set of all words ending in 00.
ii)The set of all words exceptε
iii) The set of all words that begin with 0.
3 M
Solve any one question from Q.1(d) & Q.1(e)
1(d)
What do you mean by Automate with output capability? Draw a Mealy machine equivalent to the following circuit.
7 M
1(e)
What do you mean by closure properties of regular languages? State these properties. State pumping Lemma and show that \[L=\{{a}^i{b}^i\mid i>=1\}\] is not a regular language.
7 M
2(a)
Show that the following grammar is ambiguous S\rightarrowaSbS|bSaS|ε
2 M
2(b)
What are left most and right most derivations? Explain with suitable example.
2 M
2(c)
Why CFG is most considered adequate for describing natural language? Explain with suitable example.
3 M
Solve any one question from Q.2(d) & Q.2(e)
2(d)
What do you mean by Normal forms?Reduce the grammar G /with following productions to CNF.
S→ASA|bA
A→B|S
B→c
S→ASA|bA
A→B|S
B→c
7 M
2(e)
What do you mean by useless production? Consider the grammar G=(V.T.P.S)where V,T,P,S are given as:
V={S,A,B,C,E}
T={a,b,c}
S={S}and
P consists of S→AB
A→a
B→b
B→C
E→c
Eliminate useless symbols and productions from the above grammar.
V={S,A,B,C,E}
T={a,b,c}
S={S}and
P consists of S→AB
A→a
B→b
B→C
E→c
Eliminate useless symbols and productions from the above grammar.
7 M
3(a)
What is PDA? Explain Instantaneous description of PDA.
2 M
3(b)
State the difference between PDA and the FA>
2 M
3(c)
Design a PDA to accept the language \[ \left\{ x \epsilon \{a,b\}*|n_{a}(x)>n_{b}(x) \right\}\]
3 M
Solve any one question from Q.3(d) & Q.3(e)
3(d)
Consider the grammar
S→aA
A→aABC|bB|a
B→b
C→c
Construct PDA corresponding to this grammar. Also provide moves of the PDA and the left most derivation for any string in the language defined by the grammar.
S→aA
A→aABC|bB|a
B→b
C→c
Construct PDA corresponding to this grammar. Also provide moves of the PDA and the left most derivation for any string in the language defined by the grammar.
7 M
3(e)
The intersection of two context-free languages may or may not be contest -free. Also write an algorithm for a given any context-free grammar to determine whether or not it can generate any words.
7 M
4(a)
Differentiate the purpose of the study of Turing machine with Finite Automata / Pushdown Automata.
2 M
4(b)
What is Turing - computable function? Define recursive function.
2 M
4(c)
How UTM overcomes the limitation of Turing machine?Also define UTM.
3 M
Solve any one question from Q.4(d) & Q.4(e)
4(d)
Present a Turing machine that inserts symbol # in the beginning of a string on the turing tape. Assume Σ={a,b}.
7 M
4(e)
Design a Turing machine that adds two numbers presented in binary notation and leaves the answer on the tape in binary form.
7 M
5(a)
Define P and NP problems.
2 M
5(b)
Discuss tractable and intractable problem.
2 M
5(c)
Draw and explain commonly believed relationship between class P,NP,NP- complete and NP-hard.
3 M
Solve any one question from Q.5(d) & Q.5(e)
5(d)
Define and discuss vertex cover problem.
7 M
5(e)
Discuss and explain travelling sales man problem.
7 M
More question papers from Theory of Computation