grammaire algébrique

[invitea121f130]

salut je but sur un exo si vous vouler bien m'aider
trouver une grammaire algebrique qui reconait
le languge (L) sur V={a,b,c} define par
L={a^n.b^p.c^q \ p>=n+q}
merci
-----

[invite9cf21bce]

Salut, pour pas tout te gâcher, je ne t'en mets qu'un bout :

Gauche | a Gauche b

[GuYem]

Quelqu'un pour expliquer ce qu'est une grammaire algébrique et un langage (si c'est pas trop compliqué) pour qu'on puisse mieux suivre ?

[spi100]

Un language est un ensemble de mots composés avec les lettres d'un alphabet.


Pour la grammaire, tu te donnes
1/ un alphabet terminal : les lettres qui composent le message.
2/ un alphabet non-terminal: il s'agit par exemple de SUJET, VERBE, COD. Ce sont des éléments qui permettent de décrire la structure du message mais qui n'interviennent pas dans son écriture.
3/ des règles de production: les règles de grammaires, elles indiquent par exemple que le SUJET est suivi du VERBE, puis du COD, que le SUJET est 'je, tu, il, ...'.
4/ un axiome: car il faut bien commencer par quelque chose

Ces 4 éléments définissent une grammaire formelle. Un exemple vaut mieux qu'un grand discours.
Pour un texte, la grammaire pourra être la suivante:

* L'axiome est 'TEXT'
* L'alphabet terminal est l'ensemble de tous les lettres de l'alphabet, les lettres accentuées, les majuscules, les minuscules.
* L'alphabet non terminal sera 'PHRASE, LETTRE'
* Les règles de productions :
TEXT -> PHRASE TEXT
PHRASE -> LETTRE PHRASE .
LETTRE -> a|b|...|0|...9 (| indique le ou).

Ces règles de production indiquent qu'un texte est composé de phrases. Les phrases sont composées de lettres et se terminent par un point. Les lettres sont soit a, soit b, ...

Une grammaire reconnait un language si elle permet d'en analyser tous les mots.

La théorie des grammaires formelles date des années 50, elle a été fondée par le linguiste Chomsky. Elles ont été ensuite intensivement utilisées par les informaticiens pour spécifier les langages informatiques.

C'est un peu rapide, mais j'espère que ça répond à ta question.

[A voir en vidéo sur Futura]

[martini_bird]

Salut,

pour voir si j'ai compris quelque chose, l'autre bout du message de Taar serait :

Droite | b Droite c ?

Et est le mot vide, n'est-ce pas ?

Sinon, je crois avoir compris que pour reconnaître le langage de sahdow, il faut qu'il y ait un "a" ou un "b" à gauche, et un "b" ou un "c" à droite....

Cordialement.

[invite9cf21bce]

Salut !

Bien vu martini_bird. Tu as trouvé la règle de production pour Droite.

Elle produit des mots de la forme , où q est un entier naturel.

Il manque deux règles. Il faut en réserver une à la production globale du mot souhaité.

[invitefce64850]

bonjour
je proposes le grammaire avec les régles suivantes:
S->S1.S2.S3
S1->a.S1.b+ab
S2->b.S2+b
S3->b.S3.c+bc
car si on pose p=n+m+k avec k>=0
on aura L={a^n.b^n.b^k.b^q.c^q/k,n,m>=0}.
mais j'ai en meme temps le meme probléme
la meme question mais avec L={a^n.b^m.c^q.d^p/p,q,n,m>=0 et n+q=m+p}.

[invite9cf21bce]

bonjour
je proposes le grammaire avec les régles suivantes:
S->S1.S2.S3
S1->a.S1.b+ab
S2->b.S2+b
S3->b.S3.c+bc

Je pensais à

Tout -> Gauche Centre Droite
Gauche -> | a Gauche b
Centre -> | b Centre
Droite -> | b Droite c

La tienne est identique sauf que dans la tienne, ni Gauche, ni Droite, ni Centre ne peut être vide. Du coup elle ne reconnaît pas b (par exemple). Il vaut mieux écrire :

S -> S1 S2 S3 | S2 S3 | S1 S2 | S1 S3 | S1 | S2 | S3

si tu veux couvrir le cas où la partie gauche, ou centrale, ou droite, est vide. La grammaire obtenue ne reconnaît pas le mot vide.

mais j'ai en meme temps le meme probléme
la meme question mais avec L={a^n.b^m.c^q.d^p/p,q,n,m>=0 et n+q=m+p}.

n+q=m+p n-m = p-q

Du coup tu peux réécrire ton L comme la réunion L₁ L₂, où L₁ correspond au cas où n-m 0, et L₂ au cas où m-n 0 :

L₁ = {a^m+tb^mc^qd^q+t ; m,t,q 0}

et

L₂ = {aⁿb^n+tc^p+td^p ; n,t,p 0}

Taar.

Edit : pour éviter l'ambiguïté tu peux imposer t 1 dans L₂.

[invitefce64850]

j'ai pas de probléme dans cette étape mais pour la suite est ce que je dois faire

L1={a^m+t.b^m /m,t>=0}{c^q.d^q+1 /q,t>=0} U {a^n.b^n+t /n,t>=0}{c^p+t.d^p /p,t>=0}

alors la grammaire g à
P={ S->S1+S2
S1->S3.S4
S2->S5.S6
S3->a.S3.b+a.S3+epsilon
S4->c.S4.d+d.S4+epsilon
S5->a.S5.b+b.S5+epsilon
S6->c.S6.d+c.S6+epsilon}
est ce que c'est juste et en suite je dois montrer que :L=Lg(S)?


{remarque: ("j'ai posé une question en statistique mais j'ai pas de réponse si qlq peux m'aider je le remercie d'avence" le titre c'est: fonction densité de partition ")}