Saturday, 21 March 2020

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

No comments:

Post a comment

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents