CFG signifie grammaire sans contexte. Il s'agit d'une grammaire formelle utilisée pour générer tous les modèles de chaînes possibles dans un langage formel donné. La grammaire sans contexte G peut être définie par quatre tuples comme suit :
G = (V, T, P, S)
Où,
g est la grammaire, qui consiste en un ensemble de règles de production. Il est utilisé pour générer la chaîne d'une langue.
T est l'ensemble final d'un symbole de terminal. Il est désigné par des lettres minuscules.
DANS est l'ensemble final d'un symbole non terminal. Il est désigné par des lettres majuscules.
P. est un ensemble de règles de production, qui est utilisé pour remplacer les symboles non-terminaux (sur le côté gauche de la production) dans une chaîne par d'autres symboles terminaux ou non-terminaux (sur le côté droit de la production).
constructeurs en Java
S est le symbole de début utilisé pour dériver la chaîne. Nous pouvons dériver la chaîne en remplaçant à plusieurs reprises un non-terminal par le côté droit de la production jusqu'à ce que tous les non-terminaux aient été remplacés par des symboles terminaux.
Exemple 1:
Construisez le CFG pour la langue ayant n'importe quel nombre de a sur l'ensemble ∑= {a}.
Solution:
Comme nous le savons, l'expression régulière du langage ci-dessus est
r.e. = a*
La règle de production pour l'expression régulière est la suivante :
S → aS rule 1 S → ε rule 2
Maintenant, si nous voulons dériver une chaîne 'aaaaaa', nous pouvons commencer par les symboles de début.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Là. = a* peut générer un ensemble de chaînes {ε, a, aa, aaa,.....}. Nous pouvons avoir une chaîne nulle car S est un symbole de départ et la règle 2 donne S → ε.
Exemple 2 :
Construire un CFG pour l'expression régulière (0+1)*
Solution:
entrée Java
Le CFG peut être donné par,
Production rule (P): S → 0S | 1S S → ε
Les règles sont une combinaison de 0 et de 1 avec le symbole de départ. Puisque (0+1)* indique {ε, 0, 1, 01, 10, 00, 11, ....}. Dans cet ensemble, ε est une chaîne, donc dans la règle, nous pouvons définir la règle S → ε.
Exemple 3 :
Construire un CFG pour une langue L = où w € (a, b)*.
Solution:
La chaîne pouvant être générée pour une langue donnée est {aacaa, bcb, abcba, bacab, abbcbba, ....}
La grammaire pourrait être :
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Maintenant, si nous voulons dériver une chaîne 'abbcbba', nous pouvons commencer par les symboles de début.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Ainsi, n’importe quel type de chaîne peut être dérivé des règles de production données.
xd xd signification
Exemple 4 :
Construire un CFG pour le langage L = anb2noù n>=1.
Solution:
La chaîne pouvant être générée pour une langue donnée est {abb, aabbbb, aaabbbbbb....}.
La grammaire pourrait être :
S → aSbb | abb
Maintenant, si nous voulons dériver une chaîne « aabbbb », nous pouvons commencer par les symboles de début.
S → aSbb S → aabbbb