2.1 [GATE 1987 : 2 Marks]
A context-free grammar is ambiguous if
(a) the grammar contains useless non-terminals
(b) it produces more than one parse tree for some sentence
(c) some production has two non-terminals side by side on RHS
(d) None of the aboveAnswer: (b) it produces more than one parse tree for some sentence
Concept: Ambiguity = 1 string ke 2 alag parse tree.
2.2 [GATE 1987 : 2 Marks]
Fortran is
(a) regular language (b) context free language (c) context sensitive language (d) None
Answer: (c) context sensitive language
Logic: Fortran me variable declaration check karna padta hai, jo CFL se nahi hota, CSG chahiye.
2.3 [GATE 1989 : 2 Marks]
Context free languages and regular languages are both closed under
(a) union (b) intersection (c) concatenation (d) complementation
Answer: (a) union & (c) concatenation
Trick: CFL Regular dono me Union aur Concatenation closed hai. Intersection aur Complementation me CFL fail ho j
2.4[GATE 1992:2 Marks]
Context-free languages are
(a) closed under union
(b) closed under complementation
(c) closed under intersection
(d) closed under Kleene closure
Answer: (a) & (d) – Union and Kleene closure
CFL closed: Union, Concatenation, Kleene Star. NOT closed: Intersection, Complementation.
2.5[GATE 1992:2 Marks]
If G is a CFG and w is a string of length n in L(G), how long is a derivation of w in G, if G is in Chomsky Normal Form?
(a) 2n
(b) 2n+1
(c) 2n-1
(d) n
Answer: (c) 2n – 1
Formula: CNF me har step pe 1 terminal banta hai, n terminal ke liye 2n-1 steps.
(c) closed under intersection
(d) closed under Kleene closure
Answer: (a) & (d) – Union and Kleene closure
CFL closed: Union, Concatenation, Kleene Star. NOT closed: Intersection, Complementation.