Forme normale de Chomsky

Un CFG est dans la forme normale de Chomsky si les productions sont dans les formes suivantes -

• A → a
• A → BC
• S → ε

où A, B et C sont des non-terminaux et a est terminal.

Algorithme pour convertir en forme normale de Chomsky -

Step 1 - Si le symbole de départ S se produit sur un côté droit, créez un nouveau symbole de départ S’ et une nouvelle production S’→ S.

Step 2- Supprimer les productions nulles. (Utilisation de l'algorithme de suppression de production Null discuté précédemment)

Step 3- Supprimer les productions unitaires. (Utilisation de l'algorithme de suppression de production d'unité discuté précédemment)

Step 4 - Remplacer chaque production A → B₁…B_n où n > 2 avec A → B₁C où C → B₂ …B_n. Répétez cette étape pour toutes les productions ayant deux symboles ou plus dans la partie droite.

Step 5 - Si le côté droit de toute production est sous la forme A → aB où a est un terminal et A, B sont non-terminaux, alors la production est remplacée par A → XB et X → a. Répétez cette étape pour chaque production qui se présente sous la formeA → aB.

Problème

Convertissez le CFG suivant en CNF

S → ASA | aB, A → B | S, B → b | ε

Solution

(1) Depuis S apparaît dans RHS, on ajoute un nouvel état S₀ et S₀→S est ajouté à l'ensemble de production et devient -

S ₀ → S, S → ASA | aB, A → B | S, B → b | ∈

(2) Maintenant, nous allons supprimer les productions nulles -

B → ∈ et A → ∈

Après avoir supprimé B → ε, l'ensemble de production devient -

S ₀ → S, S → ASA | aB | a, A → B | S | ∈, B → b

Après avoir supprimé A → ∈, l'ensemble de production devient -

S ₀ → S, S → ASA | aB | a | AS | SA | S, A → B | S, B → b

(3) Nous allons maintenant supprimer les productions unitaires.

Après avoir supprimé S → S, l'ensemble de production devient -

S ₀ → S, S → ASA | aB | a | AS | SA, A → B | S, B → b

Après avoir supprimé S ₀ → S, le set de production devient -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → B | S, B → b

Après avoir supprimé A → B, l'ensemble de production devient -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → S | b

B → b

Après avoir supprimé A → S, l'ensemble de production devient -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → b | ASA | aB | a | AS | SA, B → b

(4) Nous allons maintenant découvrir plus de deux variables dans l'ERS

Ici, S ₀ → ASA, S → ASA, A → ASA viole deux non-terminaux dans RHS

Par conséquent, nous appliquerons les étapes 4 et 5 pour obtenir l'ensemble de production final suivant qui est en CNF -

S ₀ → AX | aB | a | AS | SA

S → AX | aB | a | AS | SA

A → b | AX | aB | a | AS | SA

B → b

X → SA

(5)Il faut changer les productions S ₀ → aB, S → aB, A → aB

Et l'ensemble de production final devient -

S ₀ → AX | YB | a | AS | SA

S → AX | YB | a | AS | SA

A → b A → b | AX | YB | a | AS | SA

B → b

X → SA

Y → a