11 - Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky
pátek 13. května 2016
10:01
Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky.
Abeceda (značíme Σ (Sigma))
je neprázdná konečná množina, jejíž prvky nazýváme symboly, značíme Σ.
Řetězec / slovo / věta (značíme w)
konečná posloupnost symbolů abecedy
Alternativní definice:
Prázdný řetezec je řetezec
Je-li 𝑤 řetězec a a symbol abecedy pak 𝑤𝑎 je řetezec
Řetězce jsou vše, co lze získat jen a pouze aplikací pravidel 1) a 2)
Prázdný řetězec ε
řetězec neobsahující žádný symbol
Konkatenace (značíme xy)
Připojení řetězce za jiný řetězec
konkatenace je asociativní
prázdný řetězec je neutrální prvek vzhledem ke konkatenaci
Iterace (značíme 𝛴*)
množina všech řetězců nad abecedou Σ
(volný monoid nad abecedou Σ generovaný operací konkatenace)
Tj. konkatenace není komutativní jenom asociativní a neutrální prvek je prázdný řetězec
Pozitivní iterace (značíme 𝛴+)
Iterace bez prázdného řetězce
Formální jazyk (značíme L)
Jakákoli podmnožina 𝐿⊆Σ∗
Konkatenace jazyků
Rozumíme binární operaci  𝐿1⋅𝐿2=𝑥𝑦 𝑥∈𝐿1∧𝑦∈𝐿2}
Iterace jazyka
Gramatika
Gramatika (značíme G)
je čtveřice G = (N, Σ, P, S), kde:
N je konečná množina nonterminálních symbolů (nonterminálů)
Σ je konečná množina terminálních symbolů (terminálů)
P je konečná množina přepisovacích pravidel
S je počáteční (výchozí, startovací) nonterminál 𝑆∈N
Přepisovací pravidla
Podmnožina kartézského součinu 𝑵∪𝚺∗𝑵𝑵∪𝚺∗×𝑵∪𝚺∗
𝑎,𝑏∈𝑃 zapisujeme ve tvaru a→b
Přímá derivace (značíme ⇒)
Binární relace mezi řetězci u, v která platí pokud můžeme řetězce zapsat jako 𝑢=𝑔𝑎𝑑, 𝑣=𝑔𝑏𝑑 a 𝑎,𝑏∈𝑃
tj. pokud lze řetězec 𝑣 vytvořit z řetězce 𝑢 aplikací jednoho přepisovacího pravidla
Derivace ⇒+
Tranzitivní uzávěr relace přímé derivace.
tj. pokud lze vytvořit řetězec 𝑣 z řetězce 𝑢 postupnou aplikací několika přepisovacích pravidel
Derivace ⇒∗
Tranzitivní a reflexivní uzávěr relace přímé derivace
tj. pokud lze vytvořit řetězec 𝑣 z řetězce 𝑢 postupnou aplikací několika přepisovacích pravidel nebo pokud jsou řetězce stejné
Větná forma
Řetězec terminálů a nonterminálů (𝛼), které jsou iterací derivace počátečního nontermínálu (𝑆⇒*𝛼)
𝑆 je tedy taky větná forma: 𝑆⇒0𝑆
Věta
Větná forma obsahující pouze terminály.
Jazyk generovaný gramatikou
Množina všech vět, které patří do gramatiky (𝐿𝐺=𝑤 𝑆⇒*𝑤∧𝑤∈Σ*})
Chomského hierarchie klasifikace gramatik
Klasifikace je definována podle tvaru přepisovacích pravidel příslušných gramatik.
Typ 0 – obecné (neomezené) gramatiky
Zahrnují v sobě všechny formální gramatiky, generují právě ty jazyky, které mohou být rozpoznané nějakým Turingovým strojem. Tyto jazyky se někdy nazývají rekurzivně spočetné jazyky (TS se může zacykli). V případě, že je jazyk generován úplným Turingovým strojem (∀𝒘∈𝚺∗ Turingův stroj akceptuje nebo zamítá), je tento jazyk nazýván jako rekurzivní.
Jazyky: rekurzivně vyčíslitelné jazyky
Automaty: Turingovy stroje
Tvar pravidel: 𝜶→𝜷
Tedy je to to stejné, jako když jsme obecně definovali tvar pravidel programatiky.
Příklad
S → ACaB
Bc → acB
CB → DB
aD → Db
Typ 1 – kontextové gramatiky
Jazyky: kontextové jazyky
Automaty: lineárně omezené Turingovy stroje
𝐴∈𝑁
Substitujeme 𝐴 za 𝛾. α a β tvoří kontext a proto zůstávají.
Rozdíl oproti typu 2 je v kontextu. α, β tvoří kontext (proto jsou u typu 1 kontextové jazyky) a typ 2 kontext (reprezentovaný jako α, β) nemá (tedy tato tyto gramatiky generuji bezkontextové jazyky). 
Nesmí dojít ke zkrácení větné formy.
Příklad - 𝐿={1𝑛2𝑛3𝑛|𝑁≥1}
𝑆→1𝑆𝐵𝐶 //pro každou 1 vygenerujeme B a C, které budou pro 2 a 3
𝐶𝐵→𝐵𝐶
Vygeneruje se nám něco jako: 111ϵBCBCBC a tedy potřebujeme popřehazovat BCBCBC na BBBCCC
Bohuže toto nemůže být gramatikách typu 1, jelikož nevíme co je kontext a co se mění (to je typ 0)
𝐶𝑩→𝐻𝑩 //toto už jsou kontextové pravidla (C se mění na H a kontext B zůstává)
111𝐵𝑪𝑩𝐶𝐵𝐶→111𝐵𝑯𝑩𝐵𝐶
𝑯𝐵→𝑯𝐶
111𝐵𝑯𝑩𝐵𝐶→111𝐵𝑯𝑪𝐵𝐶
𝐻𝑪→𝐵𝑪
111𝐵𝑯𝑪𝐵𝐶→111𝐵𝑩𝑪𝐵𝐶 a toto se ziteruje ještě jednou a na konec dostaneme 111BBBCCC
1𝐵→12 //když je 1 (tj. kontex) před B, B převedeme na 2
Tedy 111BBBCCC převedeme na 1112BBCCC
2𝐵→22
Tady zase 1112BBCCC převedeme na 11122BCCC a to na 111222CCC
2𝐶→23
111222CCC se nám změní na 1112223CC
3𝐶→33
A nakonec je 1112223CC→11122233C→111222333 
See [link]
Typ 2 – bezkontextové gramatiky
Jazyky: bezkontextové jazyky
Tvar pravidel: 𝑨→𝜸
𝐴∈𝑁
Upřesnění: Gramatiky typu 2 mohou obsahovat 𝝐 pravidla. Přesto jsou jimi generované jazyky podmnožinou jazyků generovaných gramatikami typu 1, protože existuje algoritmus na převod libovolné gramatiky typu 2 na gramatiku bez 𝝐 pravidel.
Příklad
S → X a
X → a
X → aX
X → abc
X → ε
Typ 3 – pravé/levé lineární gramatiky
Jazyky: regulární jazyky
Automaty: konečné automaty
Tvar pravidel:
Pravá lineární: 𝐴→𝑥𝐵 𝑛𝑒𝑏𝑜 𝐴→𝑥
Levá lineární: 𝐴→𝐵𝑥 𝑛𝑒𝑏𝑜 𝐴→𝑥
𝐴, 𝐵∈𝑁
𝑥∈Σ
Případně 𝑆→𝜖 pokud S není na pravé straně žádného pravidla
Příklad
X → ε
X → a
X → aY
Další přehled: [link]
Typ CHH*
jazyk
automat
pravidlo
příklad jazyka
Typ 0
Rekurzivně vyčíslitelné
Turingův stroj
Halting problem
-
Typ 1
Lineárně ohraničený TS
Typ 2
Bezkontextové
-
Deterministické bezkontextové
Deterministický zás. automat
Typ 3
Konečný automat
 a
Každý konečný jazyk
 * Chomského hierarchie
Speciální podtypy gramatik
Stejné jako 3, ale x ∈ Σ (bez *).
Podmnožina gramatik typu 2
A → xBy nebo A → x
A, B ∈ N
x, y ∈ Σ*
Deterministické bezkontextové gramatiky
Podmnožina typu 2, jazyky přijímané deterministickým zásobníkovým automatem.
Rekurzivní gramatiky
Podmnožina typu 0. Přijímají je úplné TS (TS, které pro každý vstup rozhodnou – nikdy necyklí).
Všechny kontextové jazyk jsou rekurzivní, ale ne všechny rekurzivní jazyky jsou kontextové.
LL1 (k) gramatika
Při syntaktické analýze shora-dolů bezkontextové gramatiky občas (skoro vždy) nemáme to štěstí a pro danou levou stranu pravidla existuje více pravých stran, čili jsme v situaci, kterou nejsme schopni deterministicky rozhodnout.
Tento nedeterminismus jsme ale často schopni odstranit pomocí nápovědy, kterou je pro nás následující, dosud nezpracovaný, terminál. Pomocí něj jsme schopni ve většině případů rozhodnout, které pravidlo se má použít, tak aby byl vstup korektně zpracován - aby terminál na vrcholu zásobníku vždy odpovídal zpracovávanému znaku vstupu.
From <[link]> 
Notes
1. Otazka (predmet) (okruh): TIN - 27. Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky:
Kdo me primarne zkousel: Křivka Zbyněk, Ing., Ph.D. 
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Začal jsem popisovat chomského hierarchii, pro každý jazyk tvar pravidel, většinou jsem to napsal špatně a opravil mě. Pak chtěl jen vědět co přijímá který jazyk a zvonil budík. D 
From <[link]> 
1. Otazka (predmet) (okruh): 1.Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky.
Kdo me primarne zkousel: Janoušek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Nějak to začalo a chtěl jsem to přehodil na Chomského hiearchii, tak jsem ji začal psát na tabuly. Po zkončení v tom stresu jsem se nadechoval "co dál". Měl jsem tam chybu. Upozornil mě. Opravil jsem to hned, omluvil jsem se a on začal s otázky o rozhodnutelnosti. Nějak jsem nepochopil co chce. Ptal se na "hranici". Zeptal se na typ0, říkam že ne (že to jsou TS). Zeptal se na typ1, řekl jsem, že jsou to LOA, atd a že ano. Tak že prej kde je ta hranice, řekl jsem typ1. Což je blbě. Chtěl slyšet úplné TS. Alespoň pak (v šalině) mi došlo, že se na toto ptal. Konec - Výsledek C.
From <[link]> 
1. Otazka (predmet) (okruh): Klasifikace gramatik
Kdo me primarne zkousel: Smrz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Snova otazka, ale Smrz mi vzal uplne vitr z plachet, kdyz zacal slovy "Napiste si na tabuli nejaky kratky usek kodu v Ccku" Napsal jsem neco jako if (x == y) {a=0;}.. Pak se ptal, co z toho by byly terminaly a co neterminaly (doted jsem presne nepochopil, jak to myslel, protoze jsem mel za to, ze ve vysledku jsou vsechny ty symboly terminalni). Chtel napsat priklad pravidla gramatiky pro generovani toho kodu co jsem napsal. Tam jsem se nejak ztratil, takze presel jinam. Zacal se ptat na lexikalni analyzu, jaky automat by ji provadel (konecny), jak by se potom delala syntakticka analyza toho programu (zasobnikovym automatem).. casto jsem nechapal, co chce presne slyset a moc jsem se nechytal. Na konci rekl "tak jeste napiste tvar pravidla pro kontextovou gramatiku", zacal jsem psat na tabuli "alfa A beta" a zastavil me slovy "to staci".. mel jsem z toho dost zly pocit, kdyz jsem vysel ven.. ale nakonec za C.
From <[link]> 
2. Otazka (předmět) (okruh): 11 - TIN - Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky.
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Dobra otazka, dobry skusajuci. Najprv som mal definovat gramatiku obecne. Tu som hovoril, ze N je mnozina neterminalov atd., na co ma Meduna zastavil a chcel vediet aka mnozina (nastastie zo mna automaticky vypadlo, ze konecna a mohli sme pokracovat). Potom chcel definovat pravidla. Napisal som (NuE)*N(NuE)* -> (NuE)*. No a zvysok toho 4-minutoveho casu sa ma snazil Meduna dokopat do toho, ze tam nema byt sipka ale x. Najprv na to isiel naznakmi "mate to temer dobre, ale neco je tam jinak", na co som zneistel a snazil sa zmazat niektoru hviezdicku a zmenit ju na plus, pricom ma hned zastavil, nech si to nekazim, ze to mam dobre. A vobec som nechapal co sa po mne chce opravit. Tak isiel na to cez matiku, vytiahol zo mna, ze to pravidlo je zobrazenie, ze to je relacia a uz myslel, ze chapem. Tak povedal, ze no a ako znacime relaciu? Vtedy mi doslo, ze tam nema byt sipka, ale ani za nic ma nemohlo napadnut co tam je. Najprv som tam dal take to lezate T jak pri prechode. To som sa ale hned sam opravil, ze to je prechod. Nakoniec mi povedal, ze tam ma byt x. No a zazvonil budik, uz sa ma len rychlo opytal ako by to vyzeralo pre bezkontextovu gramatiku, co som napisal a viac nechcel.
Znamka A alebo B (nie som si isty v akom poradi mi tie znamky povedali).
From <[link]> 
1. Otazka (předmět) (okruh): 11. Klasifikace gramatik, formálních jazyků a automatů (TIN) 
Kdo me primarne zkousel: Vranić Valentino, poté Růžička Richard
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Na papírku jsem dostal otázku 11 a u toho zkratku LL1. To mě trochu znejistělo, protože jsem to při učení nikde neviděl. Zeptal jsem se, co ta zkratka znamená, ale nedostal jsem odpověď. Na to do toho zasáhl Růžička, že tohle jsme asi nebrali, ať tedy povídám obecně o tom rozdělení a čím se liší jednotlivé jazyky. Tak jsme vyjmenoval to shrnutí, jak se jmenují gramatiky, jazyky, které generují a automaty. Potom padl dotaz, jak se liší L1 a L2, tak jsem řekl, že přechodovou funkcí a napsal jsem ji pro oba dva jazyky. Trošku jsem tam dělal chyby. Chtěl po mě příklad L1 a L2 jazyků. Nakonec se ještě zeptal, jak bych dokázal, že jazyk nepatří do L2 - Pumping lemmou, k tomu mě ale musel navést.
From <[link]> 
1. Otazka (předmět) (okruh):
TIN - Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky
Kdo me primarne zkousel: doc. Holub
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Kdyby mi řekli, ať si nějakou otázku vyberu, tak bych si nejspíš vybral právě tuhle 
 Minutu na rozmyšlenou jsem nevyužil a rovnou se pustil do Chomského hierarchie. Doc. Holub se prvních pár sekund začal zrovna s někým bavit, takže jsem si mluvil pro sebe, ale potom mě již poslouchal. Začal jsem vysvětlovat od typu 3 a kreslil jsem tvar pravidel na tabuli. Dále jsem pokračoval typem 2, zmínil jsem ZA a opět napsal pravidla. Zde jsem byl tuším ještě doplněn, že ještě jedno pravidlo chybí. Jakmile to řekl, tak jsem dopsal S -> epsilon 
 Ještě se zeptal, zda jsou SKUTEČNĚ všechny regulární jazyky také bezkontextové, přičemž jsem trochu zaváhal a řekl bych že jsem asi třikrát změnil názor, jelikož se doc. Holub významně díval, čímž mě dokonale rozhodil 
 Takže jsem potom pokračoval dále - typ 1 a typ 0. U psaní pravidla pro typ 0 jsem měl třísekundové okno, ale naštěstí to naskočilo. Opět jsem ale úspěšně zapomněl na S -> epsilon 
 Až tedy na tohle a trochu nejistoty u těch inkluzí jazyků to bylo v pohodě, akorát doc. Holub na sobě nedával moc nic znát. Uteklo to skutečně rychle a žádné detaily po mně nechtěl.
From <[link]> 
1. Otazka (předmět) (okruh): Klasifikace gramatik
Kdo me primarne zkousel: Navrat
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Zacal jsem na tabuli definici gramatiky, pak jsem rekl, ze Chomska klasifikace rozdeluje gramatiky podle tvaru pravidel. Popsal obecne, popsal kontextove, u kterych jsme se trochu zadrhli na mem zapisu funkce, ale nakonec jsme se dobrali ke spravnemu zapisu. Bezkontextove a linearni byly bez problemu. Pak chtel uz jen vedet, jake automaty ke kteremu jazyku patri. Znamka B
From <[link]> 
1. Otazka (předmět) (okruh): 11. TIN - Klasifikace gramatik
Kdo me primarne zkousel: doc. Janoušek 
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Řekl jsem obecně jednu dvě věty k Chomského klasifikaci. Napsal jsem tvary pravidel všech 4 gramatik. Když jsem je napsal, zeptal se mě na automaty, které je přijímají. Po výčtu jedna přímá otázka na LOA - čím se liší od obecného TS. Dostal jsem B
From <[link]> 
1. Otazka (předmět) (okruh): 11. Klasifikace gramatik, chomského hierarchie ... 
Kdo me primarne zkousel: Horák
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Za ty 4 min jsem stihnul tak akorát vyjmenovat hierarchii, napsat pravidla pro každou třídu a říct přijímající automat, stačilo to. 
1. Otazka (předmět) (okruh): Klasifikace gramatik (TIN)
Kdo me primarne zkousel: Krivka (pripojil sa aj Hruska)
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
Otazka snov 
 Tak zacal som zadefinovanim stvorice, napisal som ten kartezsky sucin prepisovacich pravidiel, nasledne sa Krivka spytal aku klasifikaciu budem hovorit, ako sa vola, povedal som ze Chomskeho. Zacal som od Typu 3, napisal som ku kazdej gramatike prepisovacie pravidla. (V tom strese som si samozrejme zacal mylit iteracie jedna radost 
, ale Krivka naviedol tak som sa v pohode opravil). Zazvonil budik ale este mi povedal nech rychlo vymenujem automaty, ktore tieto jazyky prijimaju.
From <[link]> 
1. Otazka (předmět) (okruh): Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky. 
Kdo me primarne zkousel: Vranić Valentino
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Otazka v pohode. Zacal jsem formalni definici, typy gramatik, prepisovaci pravidla, atp.. Pak jsme debatovali o tom, kam zaradit cestinu.. Tam se pridal do konverzace i Hruby, vysledkem bylo ze se da formalne zapsat, jak jsem se ale nedozvedel.. 
 Pak syntakticka analyza shora dolu a zdola nahoru.. Tam jsem trosku tapal ale vysledku jsme se dobrali. 
From <[link]> 
2. Otazka (předmět) (okruh):
TIN - Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky.
Kdo mě primarne zkoušel: Pala Karel, Doc. PhDr., CSc. FI MUNI, Brno
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Řekl jsem jakou máme Chomského hierarchii a pak se mě hned ptal, jak se která třída jmenuje. Definoval jsem gramatiku, pak se mě ptal na zásobníkový automat, přešli jsme k derivačním stromům a skončili u strojového překladu 
 Pořád se na nějak usmíval, byl moc fajn 
 Ke konci jsem měl sucho v puse a nebyl jsem si vůbec ničím jist, tam jsem tam jenom něco kuňkal, při odchodu mi bylo doporučeno mluvit víc nahlas 
From <[link]> 
1. Otazka (předmět) (okruh): 11. Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky.
Kdo me primarne zkousel: Janousek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Otazka paradni, rekl jsem vsechno. Popsal jsem jednotlive prechody, pak mi daval doplnujici otazky (jake stroje prijimaji jednotlive jazyky, nektere problemy z nerozhodnutelnosti). Vse jsem vedel a za chvili jsme zkoncili
From <[link]> 
1. Otazka (předmět) (okruh):Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky. 
Kdo me primarne zkousel: Křivka, Rogalewicz 
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: chteli uplny zaklady, rozdeleni ,prepisovaci pravidla, automaty. za tech par minut sme se sotva dostali k typu 2
From <[link]> 
1. Otazka (předmět) (okruh): Klasifikace gramatik (TIN) (11)
Kdo me primarne zkousel: Křivka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Definoval jsem gramatiku a typy gramatik podle jejich pravidel. Pak chtěli vědět názvy odpovídajících automatů pro dané gramatiky. Křivka měl otázky na lineárně ohraničené automaty. Řekl jsem, že mají pásku podobně jako Turingovy stroje, ale že je délka pásky omezená na délku vstupního řetězce. To mu nestačilo. Správně mělo být, že je obecně délka pásky omezená lineární funkcí v závislosti na délce vstupního řetězce. Zkoušení v pohodě, byl férový. Za tuto otázku B.
From <[link]> 
2. Otazka (předmět) (okruh): 11. Klasifikace gramatik
Kdo me primarne zkousel: Janousek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Rikal sem to co vim vic, si dam na pak. No zde jsem uz vedel ale chybne jsem zapisoval nektera pravidla, a chybne odpovidal na otazky. Ptali se me jestli existuji jazyku mimo 0. Rikam "ano" a janousek to chtel rozvest. Janousek podle me nedaval najevo kdyz sem odpovedel blbe, protoze myslim ze sem odpovidal nedobre. Hruby mel otazku jestli mozne mit gramatiku ktera ma nekonecny pocet pravidel. Rikal ze ano kdyz se tak nadefinuje tak je to mozne. Malem mu vypadli oci z dulku - no ale ona nadefinovana ze ma konecny pocet pravdidel.
Hruby opet na backendu daval ferove otazky.(opravdu ferove). No reputaci jsem zlepsil asi o 1 % takze opet velmi slabe. Janousek ukoncil zkouseni taky podobne - jen to gesto nebylo tak dokonale asi si v pulce uvedomil ze hlavu uz mam davno useklou.
From <[link]> 
1. Otazka (okruh): Klasifikace gramatik
Kdo me primarne zkousel: Zemčík
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Tak tohle je lehká otázka, neměl jsem problém, Zemčík se mě pořád ptal na nějaký doplňující otázky, ale nic zákeřnýho, tohle je naprostej základ TINu, takže NP 
 Jo ale zeptal se mě k čemu vlastně gramatiky máme, pořád jsem mu dával nějaký variace na "prostě model na popis jazyků" a to pořád nebral a když se mě asi potřetí ptal, proč jazyk nepopíšeme výpisem všech řetězců, tak už mě nenapadlo říct nic jinýho než "no... to by prostě bylo moc dlouhý!" A Zemčas "jó, to jsem chtěl slyšet, jazyky můžou být nekonečný!" 
From <[link]> 
1. Otazka (okruh): Klasifikace gramatik (TIN)
Kdo me primarne zkousel: Prof. Hruška
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: no na to, že je to asi najlahsia otazka, som sa sluzne zamotal. uplne mi vypadli definicie prechodovych pravidiel.. miestami som bol taky zamotany, ze som ani nevedel, co je kart. sucin. nastastie teda Prof. Hruška sa nesnazil ma utopit, ale radil. Za C
From <[link]> 
1. Otazka (předmět) (okruh): Klasifikace jazyku (11)
Kdo me primarne zkousel: Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Chtěl vědět hierarchii a jake gramatiky to generuji a co to prijima za stroje. (L0..L4) Pak at si zvolim jeden typ a vsechno rozepisu. Zvolil sem si L0, definoval TS a veci kolem toho... Pak chtel vedet jestli jsou jeste nejake tridy mezi temito tridama, rekl jsem ze deterministicke bezkontextove a rekurzivni. Pak si vsimnul nejspis ze sem mel prekladace s Medunou, tak se me ptal co jsme v prekladacich brali za tridu, nemohl jsem si vzpomenout, byly to LL jazyky. Ale dal mi za A
From <[link]> 