Teoret-inf

˙ţtext_1_1=Jedna z mo~
ných levých derivací slova u podle gramatiky Ga odpovídající deriva

ní strom.
&text_2_1=Jedna z mo~
ných pravých derivací slova u podle gramatiky Ga odpovídající deriva

ní strom.
&text_3_1=Jedna z mo~
ných derivací slova u podle gramatiky G, která není ani levá ani praváa odpovídající deriva

ní strom.
&text_4_1=Jiná levá derivace slova u podle gramatiky G a odpovídající deriva

ní strom.Va
imn
te si, ~
e jí odpovídá jiný deriva

ní strom ne~
pY
edchozím derivacím.


text_1=Animace demonstruje převod bezkontextové gramatiky Gna zásobníkový automat s jedním stavem M.
&text_2=Množina stavů obsahuje jediný stav q.
&text_3=Do množiny vstupních symbolů ZA M zařadímeterminální symboly gramatiky G.
&text_4=Do množiny zásobníkových symbolů zařadíme všechny symbolyz množin terminálních i neterminálních symbolů gramatiky G.
&text_5=Počátečním stavem je jediný stav zásobníkového automatu q.
&text_6=Počátečním zásobníkovým symbolem ZA Mje startovací neterminál gramatiky G.
&text_7=V každém kroku libovolného výpočtu automatu M se buď: nahrazuje vrchní symbol v zásobníku řetězcem a (viz 1) nebo se odebírá symbol ze zásobníku (viz 2).
&text_8=Neterminál A na vrcholu zásobníku se nahradí řetězcem A %2B B.
&text_9=Nebo se neterminál A na vrcholu zásobníku nahradí neterminálem B.
&text_10=Neterminál B na vrcholu zásobníku nahradí řetězcem B × C.
&text_11=Nebo se neterminál B na vrcholu zásobníku nahradí neterminálem C.
&text_12=Neterminál C na vrcholu zásobníku se nahradí řetězcem (A).
&text_13=Nebo se neterminál C na vrcholu zásobníku se nahradí terminálem a.
&text_14=Terminál a se vyjme ze vstupní pásky a z vrcholu zásobníku.
&text_15=Terminál %2B se vyjme ze vstupní pásky a z vrcholu zásobníku.
2).
&text_16=Terminál × se vyjme ze vstupní pásky a z vrcholu zásobníku.
&text_17=Terminál ( se vyjme ze vstupní pásky a z vrcholu zásobníku.
&text_18=Terminál ) se vyjme ze vstupní pásky a z vrcholu zásobníku.
&text_19=Převod bezkontextové gramatiky Gna zásobníkový automat s jedním stavem M dokončen.
text_1=Animace demonstruje postup převodu bezkontextové gramatiky do Chomského normální formy.
&text_2=Nejprve zkonstruujeme pomocné množiny DX obsahující neterminály Y,tž. X =>* Y.
&text_7=Nyní budeme pomocí množin DX konstruovat novou množinu pravidel,která již nebude obsahovat pravidla typu X->Y.
&text_8=Pro každé pravidlo Y->a, kdeY je prvkem DX a a není rovno jednomu neterminálupřidáme pravido X->a.
&text_30=Pro každý terminál a zavedeme nový neterminál Xa, přidáme pravidlo Xa->a.
&text_31=Na pravé straně každého pravidla X->a, kde |a|>1nahradíme každý výskyt terminálu a neterminálem Xa.
&text_32=Pro každý terminál a zavedeme nový neterminál Xa, přidáme pravidlo Xa->a.
&text_33=Na pravé straně každého pravidla X->a, kde |a|>1nahradíme každý výskyt terminálu a neterminálem Xa.
&text_34=Každé pravidlo typu X->Y1Y2 ... Yn, kde n>1nahradíme soustavou X->Y1Z1, Z1->Y2Z2, ..., Zn-2 -> Yn-1 Yn.
&text_36=Převod do Chomského normální formy je dokončen.
text_1=Animace demonstruje postup odstraňování e-pravidelz bezkontextové gramatiky.
&text_2=Nejprve zkonstruujeme pomocnou množinu E neterminálních symbolů,které se dají přepsat na prázdné slovo e.
&text_3=Do množiny E1 zařadíme neterminály X, které lze přímo přepsat na e.
&text_6=Do množiny E2 zařadíme neterminály z množiny E1.Dále hledáme neterminály X, které dosud nepatří do množiny E2a lze je přepsat na slovo a složené z neterminálů z množiny E1.
&text_9=Do množiny E3 zařadíme neterminály z množiny E2.Dále hledáme neterminály X, které dosud nepatří do množiny E3a lze je přepsat na slovo a složené z neterminálů z množiny E2.
&text_11=Pokud jsou dvě poslední množiny En a En%2B1 stejné, je konstrukce množiny E dokončena.
&text_12=Nyní na základě E zkonstruujeme novou množinu pravidel P'.
&text_13=Projdeme všechna pravidla X->a.Vytvořime z nich pravidla X->b: b vznikne