STUPIDSID
1 (a)
Define One-to-one and Onto Functions. Also explain Compositions and Inverse of
functions.
7 M
1 (b)
Convert the following NFA- ? into FA.
7 M
2 (a)
Let M1 and M2 be the FAs pictured below, recognizing languages L1 and L2 respectively.
L2-L1.
L2-L1.
7 M
2 (b)
Define the Strong Principle of Mathematical Induction. Prove the following using mathematical Induction.
7+13+19+............+(6n+1)=n=(3n+4).
7+13+19+............+(6n+1)=n=(3n+4).
7 M
2 (c)
Prove : The language accepted by any finite automaton is regular.
7 M
3 (a)
Minimize the following DFA (If Possible).
7 M
3 (b)
Let L be the language corresponding to the regular expression (011+1)* (01)*. Find the CFG generating L.
7 M
3 (c)
Given the CFG G, find a CFG G' in Chomsky Normal form generating L(G) – { Λ}
S → A | B | C
A → aAa | B
B → bB | bb
C → aCaa | D
D → baD | abD | aa.
S → A | B | C
A → aAa | B
B → bB | bb
C → aCaa | D
D → baD | abD | aa.
7 M
3 (d)
Prove: The language pal={x∈{a,b}*|x=x2) cannot be accepted by any
deterministic pushdown automaton.
7 M
4 (a)
What is Pumping Lemma and Equivalence Relation ?
7 M
4 (b)
Design and draw a deterministic PDA accepting strings with more a's than b's. Trace it for
the string "abbabaa".
7 M
4 (c)
Define CFG and Design a CFG for the following language.
L={x∈{0,1}*|n0≠n1(x)}.
L={x∈{0,1}*|n0≠n1(x)}.
7 M
4 (d)
Attempt the following :
Draw FA for (a + b)* baaa.
Write a Regular Expression for the String of 0s and 1s in which number of 0s and 1s are even.
Draw FA for (a + b)* baaa.
Write a Regular Expression for the String of 0s and 1s in which number of 0s and 1s are even.
7 M
5 (a)
Draw the TM to copy string and delete a symbol.
7 M
5 (b)
Differentiate Regular Grammars and Context Sensitive Grammars.
7 M
5 (c)
Define:
[1] Basic complexity Classes
[2] Primitive Recursive Functions
[3] The Time and Space Complexity of a Turing Machine
[1] Basic complexity Classes
[2] Primitive Recursive Functions
[3] The Time and Space Complexity of a Turing Machine
7 M
5 (d)
Explain Polynomial Time Reductions and NP- Completeness.
7 M
More question papers from Theory Of Computation