Sunday, December 18, 2011

Context Free Grammar Question Bank

Context Free Grammar Question Bank

Question List - I




Q.1
(a)
Do as Directed.



(i)   Define CFG. What is Meaning of Context Free?
2


(ii)  List out steps to convert CFG in to CNF
2


(iii) Define Inherently Ambiguous.
1

(b)
Find out What Language is Generated by following CFG.
5


(i)  S → aT | bT | Λ.    T → aS | bS.



(ii) S → aA | bC | b.   A → aS | bB.   B → aC | bA | a.  C → aB | bS

Q.2
(a)
Define Derivation Tree or Parse Tree.
Show that following grammar is Ambiguous and Find out Unambiguous grammar for same.
S → aaaaS | aaaaaaaS | Λ.
5

(b)
Prove that The Context Free Grammar G1 with Productions
S1 → S1 + T | T  
T   → T * F | F
F   → ( S1 ) | a
is Ambiguous.
5


OR


(b)
Find out CFG for L = { x є {0, 1}* | n0(x) = n1(x) }
5




Question List - II



Q.1
(a)
Do as Directed.



(i)   List out Applications of CFG.
2


(ii)  Find out CFG for Regular Expression : (011 + 1)* (01)*
2


(iii) Define Linear Grammar.
1

(b)
Find out CFG for given Language.
5


(i)  The Set of Odd-Length string in {a, b}* with middle Symbol a.



(ii) The Set of Odd-Length string in {a, b}* whose first, middle, and last
     Symbols are all the same. 

Q.2
(a)
Define Leftmost and Rightmost Derivation.
Show that following grammar is Ambiguous and Find out Unambiguous grammar for same.
S → A | B.   A → aAb | ab.   B → abB | Λ
5

(b)
Define Nullable Variable and Unit Production.
Find out CFG with no Λ- Productions and no Unit Productions.
S → A | B | C
A → aAa | B
B → bB | bb
C → aCaa | D
D → baD | abD |aa
5


OR


(b)
Define Regular Grammar. Find a Regular Grammar generating L – {Λ}

5



Question List - III



Q.1
(a)
Do as Directed.



(i)   Define Balanced Strings of Parentheses.
2


(ii)  Define CFL. List out Application of CFL.
3

(b)
Find out CFG for
(1)  L = { ai bj ck  | j=i or j=k }
(2)  L = { ai bj   | i < 2j  }
5
Q.2
(a)
Define An Ambiguous Grammar.
Show that following grammar is Ambiguous and Find out Unambiguous grammar for same.
SABA.   A → aA | Λ.   B → bB | Λ
5

(b)
Let G be the Context Free Grammar with Productions
S → S + S | S * S | ( S ) | a
and Let G1 be the Context Free Grammar with Productions
S1 → S1 + T | T  
T   → T * F | F
F   → ( S1 ) | a
Then L (G) = L (G1).
5


OR


(b)
Define CNF. Convert following CFG in to CNF.
S → AACD.
A → aAb | Λ               
C → aC | a
D → aDa | bDb | Λ
5

No comments:

Post a Comment