Please visit, subscribe and share 10 Minutes Lectures in Computer Science

## Context Free Grammar (CFG) Solved Exercise

### Question:

Consider the grammar G = (V, Σ, R, S), where
V = {a, b, S, A},
Σ = {a, b},
R = { S → AA, A → AAA, A → a, A → bA, A → Ab }.
(a) List the set of strings that can be produced by derivations of four or fewer steps using G?
(b) Give any four distinct derivations for the string babbab using G.

### Solution:

(a) Through exhaustive search, we can find the derivations of length 4 and less as follows;
 Derivation Order in which rules are applied for each derivation S => AA => aA => aa Rule 1 => Rule 3 => Rule 3 S => AA => aA => abA => aba 1 => 3 => 4 => 3 S => AA => aA => aAb => aab 1 => 3 => 5 => 3 S => AA => bAA => baA => baa 1 => 4 => 3 => 3 S => AA => bAA => bAa => baa 1 => 4 => 3 => 3 S => AA => AbA => abA => aba 1 => 5 => 3 => 3 S => AA => AbA => Aba => aba 1 => 5 => 3 => 3 S => AA => Aa => aa 1 => 3 => 3 S => AA => Aa => bAa => baa 1 => 3 => 4 => 3 S => AA => Aa => Aba => aba 1 => 3 => 5 => 3 S => AA => AbA => abA => aba 1 => 4 => 3 => 3 S => AA => AbA => Aba => aba 1 => 4 => 3 => 3 S => AA => AAb => aAb => aab 1 => 5 => 3 => 3 S => AA => AAb => Aab => aab 1 => 5 => 3 => 3
If you observe these derivations carefully, most of them end up to same parse trees with the difference in the order of application of production rules. And, the strings that can be generated by the derivations of 4 or fewer steps are aa, aba, aab, and baa.
(b) The following are the four of the possible distinct derivations for the string babbab.

 Derivation Order in which rules are applied for each derivation S => AA => AbA => AbAb => Abab => Abbab => bAbbab => babbab 1 => 4 => 5 => 3 => 5 => 4 => 3 S => AA => AAb => AbAb => Abab => Abbab => bAbbab => babbab Try yourself S => AA => bAA => bAbA => babA => babbA => babbAb => babbab Try yourself S => AA => AbA => bAbA => babA => babbA => babbAb => babbab Try yourself

**************

Go to Natural Language Processing (NLP) home

Go to NLP Solved Exercise page