STUPIDSID
1 (a)
Define One-to-one and Onto Functions. Also explain Compositions and Inverse of functions.
7 M
1 (b)
Define NFA ' ?. Explain how to convert NFA ' ? into NFA and FA with suitable example.
7 M
2 (a)
Define Mathematical Induction Principle and Prove that for every n≥1, \[ \sum^n_{i=1} i^2=n(n+1)(2n+1)/6.
7 M
Solve any one question from Q2(b) & Q2(c)
2 (b)
Write Regular Expressions corresponding to each of the following subsets of {0,1}*
(i) The language of all strings in {0,1}* that containing at least two 0's.
(ii) The language of all strings containing both 101 and 010 as substrings.
(iii) The language of all strings that do not end with 01.
(i) The language of all strings in {0,1}* that containing at least two 0's.
(ii) The language of all strings containing both 101 and 010 as substrings.
(iii) The language of all strings that do not end with 01.
7 M
2 (c)
Prove the formula (00*1)*1 = 1+0(0+10)*11
7 M
Solve any two question from Q3(a), Q3(b) & Q3(c), Q3(d)
3 (a)
Convert the Mealy machine shown in given figure into Moore machine.
7 M
3 (b)
Check whether the given grammar is in CNF
S->bA|aB
A-> bAA|aS|a
B-> aBB|bS|b
If it is not in CNF, Find the equivalent CNF.
S->bA|aB
A-> bAA|aS|a
B-> aBB|bS|b
If it is not in CNF, Find the equivalent CNF.
7 M
3 (c)
Draw FA for accepting:
(i) The string in {0,1}* ending in 1 and not containing substring 00.
(ii) The strings with odd no of 1's and odd no of 0's.
(i) The string in {0,1}* ending in 1 and not containing substring 00.
(ii) The strings with odd no of 1's and odd no of 0's.
7 M
3 (d)
Give the context free grammar for the following languages.
(011 +1)* (01)*
7 M
Solve any two question from Q4(a), Q4(b) & Q4(c), Q4(d)
4 (a)
Explain Pumping Lemma and its applications.
7 M
4 (b)
Define Push Down Automata (PDA). 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)
Prove Kleene's Theorem Part 1 with illustration.
7 M
4 (d)
Write PDA for following languages: {aibjck|i,j,k>=0 and j=1 or j=k}.
7 M
Solve any two question from Q5(a), Q5(b) & Q5(c), Q5(d)
5 (a)
Draw the TM which recognize words of the form {anbncn|n>=1}.
7 M
5 (b)
Explain Universal Turing Machine and Church Turing Hypothesis.
7 M
5 (c)
Design Turing Machine(TM) to accept Palindrome over {a,b}, even as well as odd.
7 M
5 (d) (i)
Halting Problem
3 M
5 (d) (ii)
Primitive Recursive Function.
4 M
More question papers from Theory Of Computation