# Zapoctovy test, 29.1.2009 [10:00]

<{ForumPost(poster="zapo", timestamp=2009-01-29 15:55:42)}>
Dnes bolo nasledujuce zadanie:  
  
Na vstupe dostane program parametre: pociatocne slovo, max pocet slov, max hlbka vypoctu, subor s gramatikou  
Ulohou je nacitat subor s pravidlami (bezkontextovej) gramatiky a pre pociatocne slovo previest vypocet a vysledne terminaly (vsetky moznosti, obmadzene maximami) vypisat na standardny vystup.  
  
Pri vypocte sa postupuje zlava a pravidla su aplikovane v takom poradi, v akom boli v subore.  
  
Priklad vstupneho suboru:

    A -> aAb
    A ->

Priklad vystupu pre danu gramatiku, pociatocne slovo "A", max pocet 500 a hlbka 6:

    aaaaabbbbb
    aaaabbbb
    aaabbb
    aabb
    ab
    
    


<{/ForumPost}>

<{ForumPost(poster="Ota", timestamp=2009-01-30 11:32:29)}>
Přesné zadání vypadalo takle :

    Generovani mnoziny slov zadanych gramatikou
    
    Spusteni:
    generuj "pocatecni slovo" m n jmeno_souboru
    m - maximalni pocet generovanych slov
    n - maximalni pocet odvozeni
    soubor - obsahuje bezkontextovou gramatiku
    
    soubor vypada nasledovne:
    Kazdy radek je prazdny a nebo obsahuje prepisovaci pravidlo ve tvaru "N -> text"
    N je libovolne velke pismeno ( neterminal ) , retezec za sipkou se sklada z tisknutelnych znaku a mezery.
    Terminalem je kazdy znak krome velkych pismen.
    Gramatika generuje slovo S ze slova T, pokud slovo S vznikne ze slova T konecnym poctem aplikaci nejakeho pravidla.
    Pravidlo P -> Q muzeme na slovo T pouzit pokud T obsahuje neterminal P. Slovo po aplikaci pravidla je steje, az na to, ze tam kde bylo P je Q
    Pocatecni slovo na vstupu je tvoreno terminaly i neterminaly a slova na vystupu maji byt tvorena samymi terminaly.
    Program ma generovat vsechna slova, nicmene jejich poradi je jednoznacne dano nasledujicimi pravidly.
    - Jako prvni se vzdy prepisuje prvni neterminal ve slove ( vyrabime tzv. levou derivaci ) 
    - Pokud ma neterminal vice pravidel, pouziva se nejdrive to, ktere bylo ve vstupnim souboru prvni.
    
    Priklad:
        gramatika:
            A -> aAbA -> 
        vstupni slovo: Am = 500n = 6
    
    generuje slova
    
    aaaaabbbbb
    aaaabbbb
    aaabbb
    aabb
    ab
    

a testovací vstup (gramatika) :

    V -> R P S T.
    
    V -> V a V.
    
    P -> pes
    P -> kocka
    P -> sud
    P -> test
    
    R -> cerveny
    R -> tichy
    R -> maly
    R ->
    
    S -> leta
    S -> skace
    S -> M I
    S -> generuje
    S -> pada
    
    M -> muze
    M -> umi
    M -> smi
    
    I -> letat
    I -> skakat
    I -> generovat
    
    T -> test
    T -> 
    
    A -> aAb
    A -> X
    X -> A
    A -> stred
    
    G -> D ; G
    G ->
    
    D -> Z -> Y
    Z -> a
    Z -> b
    Z -> c
    Z -> d
    Z -> e
    Z -> f
    Z -> g
    Z -> h
    
    Y ->
    Y -> YZ
    

Šlo o to, rekurzivně nahrazovat výskyty neterminálů (velkých písmen) jiným řetězcem podle gramatických pravidel.  
Zadání bylo docela v pohodě,  navíc jsme mohli předpokládat, že vstupní soubor i vstupy od uživatele budou napsané korektně. Takže stačilo načíst vstup a pak jedna rekurzivní funkce. Mel sem to na 90 řádků ...:-)
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-01-30 15:02:21)}>
Zkoušel jsem si to napsat a těch 90 řádků je tak akorát: [http://martinvseticka.eu/index.php?sekc ... e&page=188](http://martinvseticka.eu/index.php?sekce=browse&page=188)  
Při testování se zdálo, že to funguje, tak snad je to dobře :-)
<{/ForumPost}>