STUPIDSID
1 (a) (i)
Given the relation R in A as R={(1,1), (2,2), (2,3), (3,2), (4,2), (4,4)}
is R (a) reflexive (b) symmetric (c) transitive? (d) antisymmetric?
4 M
1 (a) (ii)
Show that 2n > n 3 for n >10 by Mathematical Induction.
3 M
1 (b) (i)
Give recursive definition of each of the following sets.
a. The set T of positive integer divisible by 2 or 7.
b. The set U of all string in {0,1} * containing the substring 00.
a. The set T of positive integer divisible by 2 or 7.
b. The set U of all string in {0,1} * containing the substring 00.
4 M
1 (b) (ii)
Prove that for any every n>=0,n(n 2 +5) is divisible by 6.
3 M
2 (a)
Find a regular expression corresponding to each of the following subsets of
{0, 1}*.
i. The language of all strings that do not contain the substring 110.
ii. The language of all strings containing both 101 and 010 as substrings.
iii. The language of all strings in which both the number of 0's and the number of l's are odd.
i. The language of all strings that do not contain the substring 110.
ii. The language of all strings containing both 101 and 010 as substrings.
iii. The language of all strings in which both the number of 0's and the number of l's are odd.
7 M
2 (b)
For each of the following regular expressions, draw an FA recognizing the
corresponding language.
i. 1(01 + 10)* + 0(11 + 10)*
ii. (010 + 00)*(10)*.
i. 1(01 + 10)* + 0(11 + 10)*
ii. (010 + 00)*(10)*.
7 M
2 (c)
Let M1 , M2 and M3 be the FAs pictured in Figure below, recognizing languages L1 , L2 , and L3 respectively.
Draw FAs recognizing the following languages.
i. L1 ∪ L2
ii. L1 ∩ L2
iii. L1 - L2
iv. L1 ∩ L3
v. L3 - L2.
7 M
3 (a)
Explain Pumping Lemma and its applications.
7 M
3 (b)
Generate the Context-Free Grammars that give the following languages.
(i) {w | w contains at least three 1s} (ii) {w | w starts and ends with the same symbol}.
(i) {w | w contains at least three 1s} (ii) {w | w starts and ends with the same symbol}.
7 M
3 (c)
Write Kleene's theorem part -1.
7 M
3 (d)
For given CFG G, find Chomsky normal form:
G has productions: S -> AaA|CA|BaB A-> aaBa|CDA|aa|DC
B->bB|bAB|bb|aS C-> Ca|bC|D D->bD|Λ
G has productions: S -> AaA|CA|BaB A-> aaBa|CDA|aa|DC
B->bB|bAB|bb|aS C-> Ca|bC|D D->bD|Λ
7 M
4 (a)
Write a Turing Machine to copy strings.
7 M
4 (b)
Write PDA for following languages:
{ ai bj ck | i, j, k >= 0 and j = i or j = k}.
{ ai bj ck | i, j, k >= 0 and j = i or j = k}.
7 M
4 (c)
Write a Turing Machine to delete a symbol.
7 M
4 (d)
Write PDA for following languages:
{xε{a,b,c}*|na(x)or nac}.
{xε{a,b,c}*|na(x)or na
7 M
5 (a)
Explain Universal Turing Machine and Halting Problem.
7 M
5 (b)
Answer the following
(i) Explain time and space complexity.
(ii) Explain P and NP completeness.
(i) Explain time and space complexity.
(ii) Explain P and NP completeness.
7 M
5 (c)
Explain unbounded minimization and μ recursive functions.
7 M
5 (d)
Top down and bottom up parsing.
7 M
More question papers from Theory Of Computation