STUPIDSID
1 (a)
Define Mathematical Induction Principle and Prove that for every n ≥ 0,
[sum_{i=0}^{N} i=n(n+1)/2].
[sum_{i=0}^{N} i=n(n+1)/2].
7 M
1 (b)(i)
Suppose that Languages L1 and L2 are the subsets given below.
Where Σ={0,1}
L1 = { x | 00 is not a substring of x }
L2 = { x | x ends with 01 }
Draw FAs recognizing the following languages
1) L1-L2 2) L1∩L2.
Where Σ={0,1}
L1 = { x | 00 is not a substring of x }
L2 = { x | x ends with 01 }
Draw FAs recognizing the following languages
1) L1-L2 2) L1∩L2.
5 M
1 (b)(ii)
Show that the function f1(x,y) = x + y is primitive recursive
2 M
2 (a)
Write definition of finite automata and draw FA for the strings:
(i) The string in {0,1}* ending in 10 or 11
(ii) The string corresponding to Regular expression {11}*{00}*
(i) The string in {0,1}* ending in 10 or 11
(ii) The string corresponding to Regular expression {11}*{00}*
7 M
2 (b)
Define Context Free Grammar(CFG). Design CFG for Generating Following
Language:
(1) For Balanced Parenthesis
(2) Set of even length strings in {a, b, c, d}* with two middle symbol equal.
(1) For Balanced Parenthesis
(2) Set of even length strings in {a, b, c, d}* with two middle symbol equal.
7 M
2 (c)
Design an ambiguous grammar for if-then-else statement that also generates
if-then statement. Re-write an equivalent unambiguous grammar. Prove that
Grammar is Unambiguous by tracing 'ic1 tic2 taea'.
7 M
3 (a)
Convert NFA-^ to NFA and DFA. Initial State: A , Final State: D
| Q | δ(q,^) | δ(q,0) | δ(q,1) |
| A | {B} | {A} | Ø |
| B | {D} | {C} | Ø |
| C | Ø | Ø | {B} |
| D | Ø | {D} | Ø |
7 M
3 (b)
Define Pumping Lemma for Regular Languages. Use Pumping Lemma to show that following languages are not regular.
L = { 0n 12n / n > 0 }
L = { wwR / w ε {0,1}* }
L = { 0n 12n / n > 0 }
L = { wwR / w ε {0,1}* }
7 M
3 (c)
Convert NFA-^ to NFA and FA. Initial State: A , Final State: E
| Q | δ(q,^) | δ(q,0) | δ(q,1) |
| A | {B,D} | {A} | Ø |
| B | Ø | {C} | {E} |
| C | Ø | Ø | {B} |
| D | Ø | {E} | {D} |
| E | Ø | Ø | Ø |
7 M
3 (d)
Find CFG from given PDA that accepts the language {0n 1n }. PDA is
(Q,Σ,Γ,δ,q,Z,F) where Q={q,r},Σ={0,1},Γ={Z,X},δ
(Q,Σ,Γ,δ,q,Z,F) where Q={q,r},Σ={0,1},Γ={Z,X},δ
| State | Input | Stack | New State | Stack |
| q | 0 | Z | q | XZ |
| q | 0 | X | q | XX |
| q | 1 | X | r | ^ |
| r | 1 | X | r | ^ |
| r | ^ | Z | r | ^ |
7 M
4 (a) (i)
Given the Context Free Grammar G, find a CFG G' in Chomsky Normal
Form generating L(G) ? }
S → SS | A | B
A → SS | AS | a
B→Λ
S → SS | A | B
A → SS | AS | a
B→Λ
5 M
4 (a) (ii)
Convert following CFG to PDA,br>
S → 0S1 | 00 | 11.
2 M
4 (b)
For the language L={set of strings over alphabet {a, b} with exactly twice as
many a's as b's} design a PDA (Push Down Automata) and trace it for the
sring "abaabbaaaaabaab".
7 M
4 (c)
Given the Context Free Grammar G, find a CFG G' in Chomsky Normal Form
generating L(G) - { }
1) S → aY | Ybb | Y
X → Λ | a
Y → aXY | bb | XXa
2) S → AA
A → B | BB
B → abB | b | bb.
1) S → aY | Ybb | Y
X → Λ | a
Y → aXY | bb | XXa
2) S → AA
A → B | BB
B → abB | b | bb.
7 M
4 (d)
For the language L={ ai bj ck | i, j, k ≥ 0 and i + j = k } design a PDA (Push Down
Automata) and trace it for String "bbbbbccccc".
7 M
5 (a)
Design Turing Machine(TM) to accept Palindrome over {a,b}, even as well as
Odd.
8 M
Write short note on following:
5 (b) (i)
Universal TM
3 M
5 (b) (ii)
NP-Hard and NP-Complete Language
3 M
5 (c)
Draw Turing Machine(TM) which recognizes words of the form
{ an bn cn | n≥ 1 }.
8 M
5 (d) (i)
Halting Problem
3 M
Write short note on following:
5 (d) (ii)
Church Turing Thesis
3 M
More question papers from Theory Of Computation