Context Free Grammar (CFG) Solved Exercise

Context Free Grammar (CFG) Solved exercise, Language accepted by a CFG, List of strings accepted by a Context Free Grammar, Strings produced through derivations using grammar G

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

Go to Context Free Grammar (CFG) Formal Definition page

Context free grammar solved exercise

how to detect the languages accepted by a CFG

derivation in context free grammar