Besoin d'aide en théorie des langages - Eliminer les improductifs

[touftouf57]

Bonsoir,

Je vais passer un examen ce mardi, et j'ai obtenu le sujet de l'an dernier.
Au cours des TD, on a toujours eut des grammaires "simple" avec un seul Non terminal par règle.
Maintenant avec le sujet, j'ai des doutes sur la façon d'éliminer les improductifs
Voici la grammaire:

Code :

1
2
3
4
5
6
S -> ASa | bAc | c | epsilon | aBAc
A -> d | epsilon
B -> Bc | BAd | C
C -> Bd | B
D -> Af | epsilon

Donc pour l'élimination des improductifs je fais ainsi
N0 = Vide
N1 = (vide Union Vt)*=Vt*
N1={S,A,D} avec les règles

Code :

1
2
3
4
S ->  c | epsilon 
A -> d | epsilon
D -> epsilon

N2=({S,A,D} U Vt)*
N2={S,A,D} avec les règles

Code :

1
2
3
4
S -> ASa | bAc | c | epsilon
A -> d | epsilon
D -> Af | epsilon

N2=N1 stationnaire
Ma question est: Est-ce que j'ai bien fait de prendre la règle S-> ASa?
Est-ce que ({S,A,D} U Vt)* signifie que l'on prend les règles qui ont 1 ou plusieurs des éléments de {S,A,D} avec un ou plusieurs Vt?

C'est légèrement la panique vu que s'il y a la moindre erreur, il note 0 à l'exo.

Merci d'avance