Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Affichage des résultats 1 à 9 sur 9

grammaire algébrique

  1. sahdow

    Date d'inscription
    mai 2006
    Âge
    32
    Messages
    64

    grammaire algébrique

    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

    -----

     


    • Publicité



  2. Taar

    Date d'inscription
    décembre 2006
    Messages
    332

    Re : grammaire algébrique

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

    Gauche | a Gauche b
     

  3. GuYem

    Date d'inscription
    mars 2005
    Localisation
    Poitiers
    Âge
    36
    Messages
    2 132

    Re : grammaire algébrique

    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 ?
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.
     

  4. spi100

    Date d'inscription
    juillet 2004
    Localisation
    paris
    Âge
    45
    Messages
    1 562

    Re : grammaire algébrique

    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.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++
     

  5. martini_bird

    Date d'inscription
    octobre 2004
    Localisation
    Paris
    Âge
    37
    Messages
    6 910

    Re : grammaire algébrique

    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.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca
     


    • Publicité



  6. Taar

    Date d'inscription
    décembre 2006
    Messages
    332

    Re : grammaire algébrique

    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é.
     

  7. x1999

    Date d'inscription
    décembre 2007
    Âge
    37
    Messages
    12

    Re : grammaire algébrique

    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}.
     

  8. Taar

    Date d'inscription
    décembre 2006
    Messages
    332

    Re : grammaire algébrique

    Citation Envoyé par x1999 Voir le message
    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.

    Citation Envoyé par x1999 Voir le message
    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 L1 L2, où L1 correspond au cas où n-m 0, et L2 au cas où m-n 0 :

    L1 = {am+tbmcqdq+t ; m,t,q 0}

    et

    L2 = {anbn+tcp+tdp ; n,t,p 0}

    Taar.

    Edit : pour éviter l'ambiguïté tu peux imposer t 1 dans L2.
    Dernière modification par Taar ; 06/12/2007 à 17h36.
     

  9. x1999

    Date d'inscription
    décembre 2007
    Âge
    37
    Messages
    12

    Re : grammaire algébrique

    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 ")}
     


    • Publicité







Sur le même thème :





 

Discussions similaires

  1. si Z complexe est algébrique, alors (iz) est algébrique...
    Par thepasboss dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 20/10/2007, 19h37
  2. Avant de chanter, les baleines doivent apprendre la grammaire !
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 0
    Dernier message: 24/03/2006, 11h28
  3. bug dans le vérif. de grammaire de Word
    Par Lèf dans le forum Logiciel - Software - Open Source
    Réponses: 1
    Dernier message: 14/09/2005, 16h20