S → aSbS | bS | ε
w which of the following statements is/are true?
Correct : a,c,d
Option A - True.
Rightmost derivation of "abab":
S → aSbS → aSb(bS) → aSb(b) → a(aSbS)b(b) → a(aSb)bb → a(a)bbb — this does not work.
Correct rightmost derivation:
S → aSbS → aSb(ε) → aSb → a(aSbS)b → a(aSb(ε))b → a(aSb)b → a(a(ε)b)b = aabb — not "abab"
S → aSbS → aSb(bS) → aSb(b(ε)) → aSbb → not "abab"
S → aSbS → a(ε)bS → abS → ab(aSbS) → ab(a(ε)b(ε)) → abab
Only one such rightmost derivation exists for "abab". True.
Option B - False.
The language generated by a context free grammar is always decidable (it is recursively enumerable and decidable using CYK algorithm). False.
Option C - True.
A grammar is ambiguous if any string has more than one parse tree (or leftmost/rightmost derivation).
For "abb", two derivations exist (shown in Option D below), so the grammar is ambiguous. True.
Option D - True.
Derivation 1 of "abb":
S → aSbS → a(ε)bS → abS → ab(bS) → ab(b(ε)) → abb ✓
Derivation 2 of "abb":
S → bS → b(aSbS) → b(a(ε)b(ε)) — gives "bab", not "abb"
S → aSbS → a(ε)b(bS) → ab(b(ε)) → abb ✓ (same path)
S → aSbS → a(bS)bS → a(b(ε))b(ε) → abb ✓ (different parse tree)
Two distinct parse trees exist for "abb". True.
The correct statements are A, C and D
Similar Questions
Total Unique Visitors