15 - Transformace a normální formy bezkontextových gramatik
pátek 13. května 2016
10:20
Transformace a normální formy bezkontextových gramatik.
[link]
Derivace a derivační stromy
Gramatika (N,Σ,P,S)
Basics
Při sestavování je vždy přepsán nejlevější/nejpravější nonterminál.
Víceznačnost
Věta je víceznačná pokud existuje více derivačních stromů tvořících jednu větu.
Existují jazyky, které nelze generovat bez víceznačnosti
Gramatika, která obsahuje cykly je vždy víceznačná
ε-pravidlo
𝑨→𝝐 (přepisují nonterminál na prázdný řetezec).
A-pravidla
Všechna pravidla, která mají A na levé straně, přičemž A je nonterminál.
Jednoduchá pravidlo
𝐴→𝐵 (přepisují nonterminál na jiný nonterminál)
Zbytečné symboly
Nedostupné symboly (nelze jich dosáhnout žádným přepisem) a symboly negenerující terminální řetězce (nikdy nevytvoří větu).
Cyklus
𝐴→+𝐴
aby byly cykly možné je nutné aby gramatika obsahovala jednoduchá pravidla
Vlastní gramatika
gramatika bez zbytečných symbolů, bez cyklů a bez ε-pravidel.
Rekurzivní pravidla
rekurzivní zleva: 𝐴→𝐴𝛼
rekurzivní zprava: 𝐴→𝛼𝐴
Každý bezkontextový jazyk lze generovat gramatikou bez levé rekurze.
Všechna pravidla s levou rekurzí lze nahradit pravidly s pravou rekurzí.
Transformace
Odstranění nedostupných symbolů
Převod gramatiky (N, Σ, P, S) na gramatiku bez nedostupných stavů (N′, Σ′, P′, S)
Najdeme všechny dostupné terminály a nonterminály
i = 0
V₀ = {S} (tj. v nultém kroku je dostupný pouze počáteční stav)
repeat
Vᵢ₊₁ = Vᵢ ∪ {X | A → αXβ ∈ P ∧ A ∈ Vᵢ} (tj. do množiny dostupných přidáme všechny terminály a nonterminály, které lze získat přepisem z některého nonterminálu z množiny dostupných z předchozího kroku)
i++ (tj. přejdeme k dalšímu kroku)
until Vᵢ₊₁ = Vᵢ₋₁ (tj. končíme pokud se nám v posledním kroku množina dostupných nezměnila)
Novou gramatiku sestavíme jako:
N′ = Vᵢ ∩ N (tj. použijeme pouze dosažitelené nonterminály)
Σ′ = Vᵢ ∩ Σ (tj. použijeme pouze dosažitelené terminály)
P′ ⊂ P obsahuje pouze pravidla používající pouze symboly z Vᵢ
Odstranění NT negenerující terminální řetězce
Převod gramatiky (N, Σ, P, S) na gramatiku bez NT, které neobsahují zbytečné symboly. (N′, Σ, P′, S. 
Nalezení nonterminálů, které produkují terminální řetězce
i = 0
N₀ = ∅ (tj. v nultém kroku začínáme s prázdnou množinou nonterminálů generujících terminální řetězce)
repeat
Nᵢ₊₁ = Nᵢ ∪ {A | A → α ∈ P ∧ α ∈ (Nᵢ ∪ Σ)*} (tj. do množiny všechny nonterminály, které lze přepsat na řetězce skladádající se pouze z terminálů nebo nonterminálů, které jsou již v množině nonterminálů generujících terminální řetězce)
i++ (tj. přejdeme k dalšímu kroku)
until Nᵢ₊₁ = Nᵢ₋₁ (tj. končíme pokud se nám v posledním kroku množina nezměnila)
Vytvoříme gramatiku bez nonterminálů, které neprodukují terminální řetězce:
N′ = Nᵢ
P′ ⊂ P obsahuje pouze pravidla používající pouze symboly z Nᵢ
Odstraníme zbytečné symboly z gramatiky
--
Odstranění zbytečných symbolů
Zbytečné symboly jsou nedostupné nebo negenerují terminální řetězce. 
Alg. 4.1 je odstranění NT negenerující terminální řetězce. 
Alg. 4.2 je odstranění nedostupných symbolů. 
Screen clipping taken: 26.05.2018 8:34
Odstranění ε-pravidel
Převod gramatiky (N, Σ, P, S) na gramatiku bez ε-pravidel (N′, Σ′, P′, S′)
Sestavení množiny nonterminálů, které mohou generovat ε Nε
Postup je obdobný jako krok 1 algoritmu odstranění zbytečných symbolů pouze Nᵢ₊₁ = Nᵢ ∪ {A | A → α ∈ P ∧ α ∈ (Nᵢ ∪ {ε})*}, Nε = Nᵢ
Sestavíme novou množinu přepisovacích pravidel P′
Jestliže A → α₀B₁α₁…Bkαk ∈ P, k ≥ 0 a všechna Bᵢ jsou v Nε a žádný symbol αᵢ není v Nε pak k P′ přidej všechny prvidla tvaru A → α₀X₁α₂X₂…Xkαk kde Xᵢ je buď Bᵢ nebo ε. Nepřidává se pravidlo A → ε.
Tj. od každého pravidla sestavíme všechny možné kombinace, kde jsou jednotlivé částí přepsatelné na ε vynechány
Zavedeme nový počáteční nonterminál S′
Jestliže je S v Nε pak přidáme do P′ pravidla S′ → ε a S′ → S
Odstranění jednoduchých pravidel
Převod gramatiky bez ε-pravidel (N, Σ, P, S) na gramatiku bez jednoduchých pravidel (N, Σ, P′, S)
Pro každé A ∈ N sestrojíme množinu NA = {B | A ⇒* B}
i = 0
N₀ = {A}
repeat
Nᵢ₊₁ = Nᵢ ∪ {C | B → C ∈ P ∧ B ∈ Nᵢ}
i++
until Nᵢ = Nᵢ₋₁ (tj. končíme pokud se nám v posledním kroku množina nezměnila)
NA = Nᵢ
Sestavíme novou množinu P′
Pro všechna nejednoduchá pravidla B → α přidáme do P′ pravidla A → α pro všechna A pro něž platí B ∈ NA, tj. pro každého nejednoduché pravidlo najdeme všechny nonterminály A, které jdou jednoduchými pravidly přepsat na B, a vytvoříme všechny varianty pravidla, kde levou stranu nahradíme za A.
Odstranění levé rekurze
Odstraňování přímé levé rekurze
Následující algoritmus slouží pro odstranění přímé levé rekurze. Existuje několik jeho vylepšení. Pro každý neterminál 𝐴  s levou rekurzí, zahodíme všechna pravidla tvaru 𝐴→𝐴 a ostatní pravidla tvaru:
kde:
𝜶 jsou neprázdné řetězce neterminálů a terminálů a
𝜷 jsou řetězce neterminálů a terminálů, které nezačínají symbolem 𝑨.
nahradíme dvěma množinami pravidel, jednou se symbolem 𝑨 na levé straně:
a druhou s přidaným neterminálním symbolem 𝑨 (obvykle nazývaným „zakončení“ nebo "zbytek"):
Uvedený postup se opakuje, dokud nezůstává žádná přímá levá rekurze.
Jako příklad uvažujme sadu pravidel
kterou lze přepsat, aby se zabránilo levé rekurzi jako
𝑬𝒙𝒑𝒓𝒆𝒔𝒔𝒊𝒐𝒏→𝑰𝒏𝒕𝒆𝒈𝒆𝒓 𝑬𝒙𝒑𝒓𝒆𝒔𝒔𝒊𝒐𝒏′
𝑬𝒙𝒑𝒓𝒆𝒔𝒔𝒊𝒐𝒏→𝑺𝒕𝒓𝒊𝒏𝒈 𝑬𝒙𝒑𝒓𝒆𝒔𝒔𝒊𝒐𝒏′
[link]
Převod vlastní gramatiky (N, Σ, P, S) na gramatiku bez levé rekurze (N′, Σ, P′, S).
Nonterminály vyjádříme jako N = {A₁, A₂, …, Aₙ} tj. zvolíme pořadí jednotlivých nonterminálů.
Gramatiku budeme transformovat tak, že je-li Aᵢ → α pravidlo pak α začíná buď terminálem nebo nonterminálem Aj, který je v pořadí až za Aᵢ (j > i).
i = 1 (tj. začneme prvním nonterminálem v pořadí)
Vezmeme všechna Aᵢ-pravidla, která jsou buď ve tvaru Aᵢ → Aᵢαₓ nebo Aᵢ → βₓ, kde β nezačíná nonterminálem, který je v pořadí před Aᵢ
Přidáme nový nonterminál Aᵢ′ do N′
Všechna Aᵢ-pravidla nahradíme za:
Aᵢ → β₁ | β₂ | … | βₓ (tj. přepisy na β zachováme)
Aᵢ → β₁Aᵢ′ | β₂Aᵢ′ | … | βₓAᵢ′ (tj. pro všechny přepisy na β vytvoříme pravidla s vpravo přidaným Aᵢ′)
Aᵢ′ → α₁ | α₂ | … | αₓ (tj. u přepisů na Aᵢα vytvoříme pravidla pouze s α)
Aᵢ′ → α₁Aᵢ′ | α₂Aᵢ′ | … | αₓAᵢ′ (tj. u přepisů na Aᵢα vytvoříme pravidla s odstraněným Aᵢ a vpravo přidaným Aᵢ′
Tím dosáhneme toho, že všechna Aᵢ-pravidla začínají buď terminálem nebo nonterminálem, který je v pořadí až za Aᵢ)
Pokud jsme již prošli všechny nonterminály (i = n) končíme
i++
Pro všechny dosud procházené nonterminály Aj (1 < j < i)
Pravidlo Aᵢ → Ajα odstraníme
Pro každé Aj-pravidlo (Aj → β) vytvoříme Aᵢ → βα, tj. vezmeme všechna Aᵢ-pravidla, jejichž pravá strana začíná nonterminálem Aj, který je v pořadí před Aᵢ, a nahradíme je za pravidla ve kterých je Aj nahrazeno všemi řetězci na které jej lze přepsat.
Jdeme na krok 2
Chomského normální forma je tvar formální gramatiky ve které jsou všechna odvozovací pravidla tvaru:
A → BC
A → a
S → ε pokud ε ∈ L(G) a S nesmí být na pravé straně žádného přepisovacího pravidla.
a je NEterminál, velká písmena jsou terminály.
derivační strom CNF je binární
Derivační strom (= syntaktický strom)
Vnitřní uzly jsou neterminály, tedy prvky z 𝑵
Koncové uzly jsou terminály 𝚺
Kořen stromu je 𝑺
Hrany odpovídají přepisovacím pravidlům gramatiky P
Označení koncových uzlů zleva doprava tvoří větnou formu (nebo větu)
Každé derivaci přísluší jeden derivační strom, ale jednomu stromu může příslušet více derivací (více způsobů jak sestavit stejný strom - různé pořadí v jakém byly vybírány nonterminály pro přímé derivace).
Převod vlastní gramatiky bez jednoduchých pravidel (N, Σ, P, S) na gramatiku v CNF (N′, Σ, P′, S′)
Množina P′ obsahuje všechny pravidla z P ve tvaru A → BC a A → a, případně S → ε.
Každé pravidlo tvaru A → X₁X₂…Xk (k > 2) přepíšeme do P′ jako sérii pravidel:
A → X₁X₂′
X₂′ → X₂X₃′
Xk₋₁′ → Xk₋₁Xk
Zavedeme nové non-terminální symboly A → X₂′…Xk₋₁′ 
(tj. pravidla mající pravou stranu delší než dva prvky rozdělíme na navazující sérii pravidel majících napravo jen dva prvky)
Ve všech pravidlech v P′ které nejsou ve tvaru A → a, kde se vyskytují na pravé straně terminály, nahradíme tyto terminály a za nové non-terminály A′ a přidáme pravidlo A′ → a 
(tj. nepovolená pravidla s terminály na pravé straně upravíme tak, že terminál nahradíme nonterminálem, který se přepisuje na původní terminál)
Greibachové normální forma (GNF)
Graibachové normální forma (GNF) je tvar formální gramatiky, ve které mají všechny odvozující pravidla tvar:
A → aα kde α ∈ N* //tedy A→aA1A2…An
S → ε pokud ε ∈ L(G) a S nesmí být na pravé straně žádného přepisovacího pravidla
jestli na konci stačí pouze jeden nonterminál (odpovědí je, že nestačí, jinak by to byla regulární gramatika). 
Nejsou žádná ε pravidla.
k cemu se pouziva Chomskeho -> dukaz pumping lemma a syntaktická analýza. 
Převod vlastní gramatiky bez levé rekurze (N, Σ, P, S) na gramatiku v GNF (N′, Σ, P′, S′):
Seřadíme všechny nonterminály tak, aby pravá strana žádného přepisovacího pravidla nezačínala nonterminálem, který je v pořadí před přepisovaným nonterminálem. (v podstatě stejná pořadí v jakém máme nonterminály během algoritmu odstranění levé rekurze): N = {A₁, A₂, …, Ak}
Postupně pro všechny nonterminály Aᵢ od Ak₋₁ sestupně po A₁:
Pro každé pravidlo Aᵢ → Ajα:
Odstraň toto pravidlo
Pro všechna Aj-pravidla (Ajα → β) vytvoř nová pravidla ve tvaru Aᵢ → βα (tj. všechna pravidla jejichž pravé strana začíná nonterminálem rozepíšeme tento nonterminál na všechny možnosti na jaké jej lze přepsat)
Po dokončení tohoto kroku všechny pravidla mají pravou stranu začínající terminálem.
Ve všech pravidlech v P′ ve kterých se na pravé straně vyskytují terminály na jiné než první pozici nahradíme tyto terminály a za nové non-terminály A′ a přidáme pravidlo A′ → a (tj. nepovolená pravidla s terminály na pravé straně upravíme tak, že terminál nahradíme nonterminálem, který se přepisuje na původní terminál)
Příklady
Příklad 1
Gramatiku G = ({A, B, C}, (a, b, c}, P, A) s pravidly
A → Ba | a
B → BbC | C
C → Cc | A
převeďte algoritmicky do Greibachové normální formy a Chomského normální formy.
Odstranění ε-pravidel: žádné nejsou.
Odstranění levé rekurze:
A → a | aA′
A′ → a | C′a | B′a | C′B′a | aA′ | C′aA′ | B′aA′ | C′B′aA′
B → C | CB′
B′ → bC | bCB′
C → A | AC′
C′ → c | cC′
Relace uspořádání: A′ < C′ < B′ < B < C < A
Dosazení v pořadí inverzním k relaci uspořádání:
A → a | aA′
C → a | aA′ | aC′ | aA′C′
B → a | aA′ | aC′ | aA′C′ | aB′ | aA′B′ | aC′B′ | aA′C′B′
B′ → bC | bCB′
C′ → c | cC′
A′ → a | ca | cC′a | bCa | bCB′a | cB′a | cC′B′a | aA′ | caA′ | cC′aA′ | bCaA′ | bCB′aA′ | cB′aA′ | cC′B′aA′
Upravíme pravidla do Greibachové normální formy:
A → a | aA′
C → a | aA′ | aC′ | aA′C′
B → a | aA′ | aC′ | aA′C′ | aB′ | aA′B′ | aC′B′ | aA′C′B′
B′ → bC | bCB′
C′ → c | cC′
A′ → a | cA″ | cC′A″ | bCA″ | bCB′A″ | cB′A″ | cC′B′A″ | aA′ | cA″A′ | cC′A″A′ | bCA″A′ | bCB′A″A′ | cB′A″A′ | cC′B′A″A′
A″ → a
Vlastní gramatika: zadaná gramatika už vlastní je.
Bez jednoduchých pravidel:
NA = {A}
NB = {A, B, C}
NC = {A, C}
A → Ba | a
B → BbC | Cc | Ba | a
C → Cc | Ba | a
A → Ba′ | a
B → B<bc> | Cc′ | Ba′ | a
C → Cc′ | Ba′ | a
a′ → a
c′ → c
<bc> → b′C
b′ → b
Příklad 2
Mějme gramatiku G₅ = ({S, A, B, C}, {a, b, c}, P, S), kde
P:
S → aACa
A → B | a
B → C | c
C → Cc | bC | ε
Převeďte gramatiku G₅ algoritmicky do Chomského normální formy.
Bez ε přechodů:
Nε⁰ = ∅
Nε¹ = {C}
Nε² = {C, B}
Nε³ = {C, B, A}
Nε⁴ = {C, B, A} = Nε³ = Nε
S → aACa | aAa | aCa | aa
A → B | a
B → C | c
C → Cc | b | bC | c
Bez jednoduchých pravidel:
NS⁰ = {S}
NS¹ = {S} = NS⁰ = NS
NA⁰ = {A}
NA¹ = {A, B}
NA² = {A, B, C}
NA³ = {A, B, C} = NA² = NA
NB⁰ = {B}
NB¹ = {B, C}
NB² = {B, C} = NB¹ = NB
NC⁰ = {C}
NC¹ = {C} = NC⁰ = NC
S → aACa | aAa | aCa | aa
A → Cc | a | b | bC | c
B → Cc | b | bC | c
C → Cc | b | bC | c
Vlastní gramatika (odstranění zbytečných a nedostupných symbolů):
V₀ = {S}
V₁ = {S, a, A, C}
V₂ = {S, a, A, C, c, b}
V₃ = {S, a, A, C, c, b} = V₂ = V
S → aACa | aAa | aCa | aa
A → Cc | a | b | bC | c
C → Cc | b | bC | c
G = ({S, <ACa>, <Aa>, <Ca>, A, C, a′, b′, c′}, {a, b, c}, P, S)
P:
S → a′<ACa> | a′<Aa> | a′<Ca> | a′a′
<ACa> → A<Ca>
<Aa> → Aa′
<Ca> → Ca′
A → Cc' | a | b | b′C | c
C → Cc' | b | b′C | c
a′ → a
b′ → b
c′ → c
Převeďte gramatiku G₅ algoritmicky do Greibachové normální formy.
Vlastní gramatika:
Viz převod do Chomského normální formy
Odstranění levé rekurze (S < A < C):
S → aACa | aAa | aCa | aa
A → Cc | a | b | bC | c
C → b | bC | bC′ | bCC′ | c | cC′
C′ → c | cC′
G = ({S, A, C, C′, a′, c′}, {a, b, c}, P, S)
P:
S → aACa′ | aAa′ | aCa′ | aa′
A → a | b | bC | bC′c′ | bCC′c′ | bCc′ | bc′ | c | cC′c′ | cc′
C → b | bC | bC′ | bCC′ | c | cC′
C′ → c | cC′
a′ → a
c′ → c
Notes
2. Otazka (predmet) (okruh): Transformace a normální formy bezkontextových gramatik
Kdo me primarne zkousel: Smrz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Začal jsem mluvit obecně o transformacích, že máme nějaké vlastní gramatiky a jaké převody se musí provést k jejich dosažení. Po druhé větě mě ale Smrž okamžitě přerušil a řekl, ať rovnou napíšu které to jsou a jejich tvar, což jsem bezproblému udělal. Potom mi řekl, ať napíšu jazyk a^n b^n a snažil se mě zvyklat k tomu, abych řekl že je to regulární, ale nedal jsem se. K tomuto jazyku jsem měl napsat gramatiku, kde jsem nejprve začal psát nesmysly (S -> AB), přičemž mě hned zastavil že takto to půjde hodně těžko. Tak jsem se hned vzpamatoval a napsal to hned dobře. Potom po mě chtěl abych ji převedl do CNF, což byla brnkačka, ale v nervozitě jsem to tam koktal a motal páté přes deváté. Zazvonil budík, ale zkoušení pokračovalo ještě dobrých deset minut, přičemž se ze mě snažil nejprve vytáhnout, že derivační strom CNF je binární a potom ještě otázku (přesně si už nepamatuju), kolik nejméně neterminálu musím mít na pravých stranách aby to byla bezkontextová gramatika. To ze mě tahal 5 minut, načež jsem mu řekl, že prostě nevím na co se mě ptá, potom jsem plácl že asi stačí jeden, ale to mi řekl, že právě ne, že to je regulární. Po tomhle řekl, že mu to stačí a ať jdu ven. Tahle otázka pak byla taky za C.
From <[link]> 
1. Otazka (předmět) (okruh): 15. Transformace a normální formy bezkontextových gramatik. 
Kdo me primarne zkousel: Janoušek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Chtěl jsem začít definicí gramatiky, ale Janoušek mě hned usměrnil na normální formy. Chomského jsem napsal v pohodě, pak jsem řekl, že napíšu Gronbachovu a na to mě hned upozornil, že to byla žena a že se to skloňuje jinak. To mě úplně vykolejilo a měl jsem okno. Pak se zeptal na název nějakého algoritmus, který se používá(podle mě jsme to ani nebrali ten název). Při mém pokusu o správný tvar pravidel řekl, že jsem napsal pravou rekurzy a jestli vím, jak se jí zbavit. To už jsem se jenom modlil. Nakonec za E.
From <[link]> 
1. Transformace a normální formy bezkontextových gramatik. (TIN) (15):
Kdo me primarne zkousel: Smrž
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Nejdříve chtěl vědět, co jsou to vlastně bezkontextové gramatiky, jaký mají tvar pravidel, k čemu jsou nám užitečné. Následně došlo na normální formy, nejdříve jsem popisoval CNF, tady ho zajímalo, čím je význačná, opět tvar pravidel. Následovala GNF, tam jsem se trochu zamotal ke konci s tím, že chtěl vědět, jestli na konci stačí pouze jeden nonterminál (odpovědí je, že nestačí, jinak by to byla regulární gramatika). Také ho zajímalo jakým způsobem získám gramatiku bez epsilon pravidel, dostal jsem příklad, zapsal ho na tabuli a měl jsem určit počet nových pravidel.
Celkově za B.
From <[link]> 
2. Otazka (předmět) (okruh): Transformace a normální formy bezkontextových gramatik. 
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Měl jsem začít tím jaké jsou transformace, co je BKG (zde jsem v souladu s mým celkovým projevem zapoměl říct že gramatika je ntice, k tomu mě meduna pošťouchl), popsat pravidla. Zasekl jsem se trochu u definice jednotlivých částí (nepřesný výrazy, spíš hovorový než formálně správný). Tlačil čas, takže jsem měl napsat GNF, a pak k čemu obecně slouží normální formy (prakticky (překladače), i teoreticky (důkazy))
From <[link]> 
1. Otazka (předmět) (okruh): TIN 15. Transformace a normální formy bezkontextových gramatik.
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
*) Definujte gramatiku -> napsal jsem ctverici, zacal popisovat, sem tam komentar, ze to neni formalni popis. 
*) Pak poznamka, ze toto neni bezkontextova gramatika (nevim jestli jsem se preslechl ja nebo to profesor Meduna nerekl, ze chce bezkontextovou) -> upravil jsem tvar pravidel. 
*) Jake zname transformace -> odstraneni epsilon pravidel, jednoduchych pravidel, leve rekurze (u toho se trochu zastavil a chtel souvislost s top-down syntaktickou analyzou). 
*) Jake zname normalni formy -> Chomskeho, Graibachove
*) definovat Chomskeho -> napsal jsem tvar pravidel
*) k cemu se pouziva Chomskeho -> dukaz pumping lemma
*) a prakticke pouziti Chomskeho -> chvily jsem vahal a pak jsem v podstate zaroven s prof. Medunou rekl k syntakticke analyze 
From <[link]> 
1. Otazka (předmět) (okruh): 15. Transformace a normální formy bezkontextových gramatik.
Kdo me primarne zkousel: Smrž
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Touhle otázkou jsem začínal. Ani jsme se nedostali moc do hloubky, chtěl jen vidět jak vypadá GNF a CNF, plus nějaké věci kolem, to jsem veděl. Pak odstranění epsilon pravidel, to jsem taky jakž takž popsal. Nakonec ze mě chtěl dostat něco v souvislosti s převodem bezkontextových gramatik do GNF, ale za celou dobu jsem pořádně nepochopil co chce a ani teď to nevím:) Nakonec z toho vykrystalizovala otázka na kterou se dalo odpovědět buď ano nebo ne. Já řekl ano, ale bylo to ne:) I díky tomu nakonec z téhle otázky za C.
From <[link]> 
2. Otazka (okruh): 15. Transformace a normální formy bezkontextových gramatik.
Kdo me primarne zkousel: Krivka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Zacal jsem mluvit o tom, jake znam transformace gramatik. Co je vstup. Co je vystup. Jaky je mezi temi gramatikami vztah. Potom chtel vedet, jak funguje odstraneni leve rekurze. Tady jsem trosku zaperlil. Odpovedi mi byl Krivkuv zmateny pohled. Ale princip jsem znal, tak se to zvladlo. Take ho zajimalo, jak vypada Chomskeho NF. Bylo to celkem v pohode. Opet vse spis obecnejsi povidani. Slo o myslenku a ne o formalismy. Moc se v tom nepitval. Znamka C.
From <[link]> 
1. Otazka (okruh): Bezkontextové gramatiky a transformace (tak nějak to bylo na tom lístečku napsané) - asi to měla být 15. Transformace a normální formy bezkontextových gramatik
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Zadání té otázky mě trochu rozhodilo, měl jsem spíš naučené ty normální formy a transformace, ale tak chtěl jsem teda začít nějak obecně od té gramatiky. A do toho se Meduna už začal dál vyptávat na jazyk té gramatiky a derivace atd...všechno formálně. Nakonec k těm normálním formám jsme se dostali jenom při poslední otázce po budíku: Jaké teda máme ty normální formy? Takže podle mě věci totálně mimo okruh... Ale Meduna hodně pomáhal.
From <[link]> 
1. Otazka (okruh): Transformace a normální formy bezkontextových gramatik.
Kdo me primarne zkousel: Havlice, Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Havlice chtěl jen jaké ty transformace jsou a proč se to dělá a kde se to používá. Tam jsem sem tam trošku zasekl, ale nakonec jsem řekl, co chtěl. Potom Havlice řekl, že už nemá další otázky, ale na to Češka řekl, že to vypadá, že aspiruju na lepší hodnocení a že mi to nedá zadarmo. Trošku mě pak podusil na epsilon pravidlech, ale spíš tak přítelsky.
From <[link]> 
1. Otazka (okruh): Transformace a normální formy bezkontextových gramatik
Kdo me primarne zkousel: Havlice (externista)
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal sme obecně co to je bezkontextová gramatika. Co to je transformace gramatiky. Chtěli pár příkladů transformací. Algoritmy vůbec jen chtěl stručně popsat princip odstranění zbytečných symbolů. Trochu mě zarazil, když se zeptal co se dá vyvodit z toho, když v gramatice najdeme zbytečné symboly (chtěl slyšet, že to poukazuje na možnou chybu při návrhu gramatiky, což sem tak nějak uhodl). Pak chtěl vědět čemu vadí levá rekurze (nejde to aprsovat metodou shora dolů). K normálním formám sme se už vůbec nedostali.
From <[link]> 