Grammaire contextuelle

leeween

Bonjour je suis étudiante et récemment nous avons commencé un nouveau chapitre sur la grammaire contextuelle avec lequel j'ai beaucoup de mal. Nous avons fait un exercice sauf que je ne comprends pas la correction et j'aimerais savoir si quelqu'un peut m'expliquer. Voici le sujet.

Soit la grammaire contextuelle S->SS+ | SS * | a. Montrer comment la chaîne aa+a* peut être produite par cette grammaire.

Voici la correction.

S->SS*->Sa*->SS+a*->Sa+a*->aa+a*

Je ne comprends pas pourquoi on commence par SS* et pas par exemple par SS+, je ne comprends pas pourquoi les S deviennent des a et je ne comprends pas ce que signifie le symbole  " | ".
Je vous remercie d'avance pour votre aide

raoul.S

Je crois ne pas me tromper en disant que la notation $S\to SS^{+}\mid SS^{*}\mid a$ signifie que dans un mot tu peux remplacer le symbole $S$ par $SS^{+}$ ou par $SS^{*}$  ou par $a$ tout simplement.

$S$ est toujours le symbole de départ. Le but est de construire des mots à partir de ce symbole en appliquant les règles de remplacement ci-dessus.

On a :
1) À partir de $S$ j'obtiens le mot $SS^{*}$ (j'applique la règle de remplacement $S\to SS^{*}$)
2) À partir de $SS^{*}$ j'obtiens le mot $Sa^{*}$ (j'applique la règle $S\to a$ qui remplace $S$ par $a$ au deuxième $S$ du mot de départ)
3) À partir de $Sa^{*}$ j'obtiens $SS^{+}a^{*}$ en appliquant le règle $S\to SS^{+}$
etc.

john_john

A première vue, l'ensemble des productions est l'ensemble des expressions <<arithmétiques>> construites à partir des opérateurs binaires $+$ et $*$ et de l'unique opérande $a$ ; les opérateurs sont postfixés (notation polonaise).