NOTE: For remedial
GOVERNMENT
ENGINEERING COLLEGE, PATAN
CSE Department
Assignment - 2
Sub: TOC (160704)
SEM: 6th G & H
_____________________________________________________________________________
1. Prove
that the following CFG is Ambiguous.
S-> S + S | S * S | (S) | a
Write the unambiguous CFG for the above grammar.
Draw Parse tree for the string
a + a * a.
2. Design a
CFG(Context Free Grammar) for the following language. L = { 0i 1j
0k / j > i+k }
3. For the
language L = { xcxr/ x Є {a,b}* } (Palindrome with middle character=c), Design a PDA(Push Down
Automata) and trace it for string “abacaba”.
4. Convert
following CFG to equivalent Chomsky Normal Form (CNF).
S -> AACD | ACD | AAC | CD | AC | C
A -> aAb | ab
C -> aC | a
D -> aDa | bDb | aa | bb
5. Design
and draw deterministic PDA accepting strings of the language
L = {x Є {a, b}* | na(x) > nb(x)}. Trace it for the string “aababaab”.
6. Write
short notes on the following.
(i) Equivalence Relation.
(ii) Universal Turing Machine.
(iii) The Sets P, NP, PSpace and
NPSpace.
|
(iv)
Top Down Parsing And Bottom Up Parsing.
|
|
|
(v) Application of Pumping Lemma.
(vi) Basic Complexity Classes.
(vii) μ Recursive Functions.
(viii) Primitive Recursive Operation & Function.
(ix) Time and space complexity.
(x) NP complete problem
(xi) Halting
Problem.
7. Write theorem: If L1 and L2 are context free
languages, then the language L1UL2, L1L2 and L1* are also CFLs.
8. Answer the following
1. Find context free grammar generating following
language {aibjck | i = j or i = k}
2. Show that CFG S-> a|Sa|bSS|SSb|SbS is ambiguous.
3. find an equivalent unambiguous grammar for
following:
S-> A|B
A ->aAb|ab
B-> abB|Ʌ
9. Write TM accepting
Palindrome.
10. Write transition table for PDA recognizing following
language:
{ aibjck | j = i or j = k }.
11. Write TM accepting {ss | s
ϵ {a,b}*}
12. Define Context
Free Grammar (CFG). Describe the language accepted by following CFG: S ->aSa | bSb | a | b | Λ
13. For the language L=
{xcxr /
xЄ{a,b}*} design a PDA(Push Down Automata) and trace it for string “bacab”.
14. Convert following CFG to
equivalent Chomsky Normal Form(CNF).
S->AACD | ACD | AAC |
CD | AC | C
A ->aAb | ab
C ->aC | a
D ->aDa | bDb
| aa | bb
15. .Design and draw a
deterministic PDA accepting strings with more a’s than b’s. Trace it for the
string “abbabaa”.
16. Prove that √2
(square root of 2) is Irrational by method of Contradiction.
17. Prove: There are context-free languages L1 and L2
so that L1 ∩ L2 is not a CFL and there is a CFL L so that L’
is not a CFL
18. Given the CFG G, find a CFG G’ in
Chomsky Normal form generating
L(G) – { Λ}
S -> AaA | CA | BaB
A-> aaBa | CDA
| aa | DC
B -> bB | bAB | bb | aS
C -> Ca | bC | D
D->
bD | Λ
19. Define PDA and design PDA for L={
x Є {a,b}*|| na (x) > nb (x)}.
20. Explain Derivation Tree,
Expression Tree and Ambiguity with Example.
21. Draw the TM for L = {ss | s Є (a, b)*}
22. Explain Pumping Lemma and its applications.
23. 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}
24. 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|Λ
25. Write a Turing Machine to copy strings.
26. Write a Turing Machine to delete a symbol.
27. Write PDA for following languages: { x ∈ { a,b,c}* | | na (x) < nb (x) or | na
(x) < nc(x) }.
28. Let L be the language corresponding to the regular
expression (011+1)* (01)*. Find the CFG generating L.
29. The language pal= { x ∈ {a, b}* | x = xr } cannot be accepted by any deterministic pushdown
automaton.
30. Design and draw a deterministic PDA accepting strings with
more a’s than b’s. Trace it for the string “abbabaa”.
|
|
|
|
|
|
No comments:
Post a Comment