Ülesanne 4.

  1. Stringi a+(a*(a+a)+a) tuletuspuu oleks selline

  2. Üldjuhul kahjuks siiski ei saa, sest sellisel juhul oleks vaja lõpmatult palju mitteteminaale. Mitteterminaale on nii palju vaja aga järgmisel põhjusel: sõna tuletatakse kasutades paremtuletust. Viimane aga ei võimalda kontrollida seda, mida me oleme juba teinud (st. kui palju on sulge üksteise sees avatud). Et tegevuse sulgude avamise üle saada kontroll, on vaja eraldi mitteterminaale ja produktsioone, mis on mõeldud iga uue sisemiste sulgude taseme jaoks eraldi nii sulge avama kui ka sulgema.
  3. Pakun lahenduseks järgmise grammatika. Võtsin endale vabaduse loobuda looksulgudest produktsioonide hulga ümber ja ka seletada seda, milleks iga mitteterminaal on kasutusele võetud.
  4. Produktsioonid Produktsiooni vasakpoolse mitteterminaali sissetoomise põhjus
    S->A S on lähtesümbol, temast saab kõik alguse
    A->a A->aB A->aC A->D A on terminaali 'a' sissetoomiseks sulgude tasemel 0
    B->+A B->+D B on terminaali '+' sissetoomiseks sulgude tasemel 0
    C->*A C->*D C on terminaali '*' sissetoomiseks sulgude tasemel 0
    D->(F D->(J D on sulgude taseme 1 avamiseks
    E->) E->)B E->)C E on sulgude taseme 1 lõpetamiseks
    F->(H F->(M F on sulgude taseme 2 avamiseks
    G->)E G->)K G->)L G on sulgude taseme 2 lõpetamiseks
    H->(P H on sulgude taseme 3 avamiseks
    I->)G I->)N I->)O I on sulgude taseme 3 lõpetamiseks
    J->aE J->aK J->aL J on terminaali 'a' sissetoomiseks sulgude tasemel 1
    K->+F K->+J K on terminaali '+' sissetoomiseks sulgude tasemel 1
    L->*F L->*J L on terminaali '*' sissetoomiseks sulgude tasemel 1
    M->aG M->aN M->aO M on terminaali 'a' sissetoomiseks sulgude tasemel 2
    N->+H N->+M N on terminaali '+' sissetoomiseks sulgude tasemel 2
    O->*H O->*M O on terminaali '*' sissetoomiseks sulgude tasemel 2
    P->aI P->aQ P->aR P on terminaali 'a' sissetoomiseks sulgude tasemel 3
    Q->+P Q on terminaali '+' sissetoomiseks sulgude tasemel 3
    R->*P R on terminaali '*' sissetoomiseks sulgude tasemel 3