13 - Konečné automaty
pátek 13. května 2016
10:14
Konečné automaty (jazyky přijímané jazyky KA, varianty KA, minimalizace KA, Mihill-Nerodova věta).
Definice (nedeterministického) KA (NKA)
Q – konečná množina stavů
Σ – konečná vstupní abeceda
δ – funkce přechodu (zobrazení 𝑸 × 𝜮 → 𝟐𝑸)
To je 𝟐𝑸 je asi potenční množina, tedy množina, která obsahuje všechny podmnožiny množiny 𝑄.
q₀ – počáteční stav (𝑞₀∈𝑄)
F – množina koncových stavů (𝐹⊆𝑄)
Konfigurace
Dvojice 𝑞, 𝑤∈𝑄×𝛴* tj. stav a zbývající vstup
Počáteční konfigurace
Dvojice (𝑞₀, 𝑤) tj. počáteční stav a celý vstup
Koncová konfigurace
Dvojice (𝑞 ∈ 𝐹, 𝜀) tj. některý koncový stav a prázdný vstup
Přechod ⊢
Změna jedné konfigurace na jinou jednou aplikací funkce přechodu (přečtení jednoho znaku ze vstupu a změna stavu)
⊢ᵏ – 𝑘 přechodů po sobě
⊢⁺ – libovolný počet přechodů (> 0) (tranzitivní uzávěr relace přechodu)
⊢* – libovolný počet přechodů (tranzitivní a reflexivní uzávěr relace přechodu)
Jazyk přijímaný KA
tj. množina všech řetězců pro které KA přejde z počáteční do koncové konfigurace
Rozlišitelné stavy
Stavy jsou rozlišitelné pokud existuje nějaký vstupní řetězec pro který automat z jednoho stavu skončí v koncovém stavu a z druhého ne.
Formálně: Stavy p, q jsou rozlišitelné pokud ∃ 𝑤∈𝛴*:(𝑝, 𝑤)⊢* (𝑝₁, 𝜀)∧(𝑞, 𝑤)⊢*(𝑞₁, 𝜀) a právě jeden z 𝑝₁, 𝑞₁ je v 𝐹.
Jazyky přijímané KA jsou jazyky třídy 3 Chomského hierarchie (regulární jazyky).
Varianty konečných automatů
Rozšířený KA
Liší se definice funkce přechodu 𝛿: (𝑄 × (𝛴 ∪{𝜺})→2𝑄, tj. je rozšířený o ε-přechody.
Deterministický konečný automat (DKA)
Liší se definice funkce přechodu 𝜹:𝑸×𝜮→𝑸∪{𝒏𝒆𝒅𝒆𝒇}, nedef ∉ Q, tj. pro každou konfiguraci existuje jen jeden možný přechod.
Jsou ekvivalentní NKA
Každý NKA lze převést na DKA
Funkce přechodu je definována pro všechny kombinace vstupního znaku a stavu. tj. δ je totální funkcí na Q × Σ.
Pro případy, kdy neúplný KA nemohl pokračovat (a tím odmítl vstup) zavádíme speciální nekoncový stav ERROR (SINK, T, …) do kterého, když se automat dostane tak jej nemůže opustit (tj. po přečtení celého vstupu je stále v nekoncovém stavu a tak vstup odmítne).
DKA bez nedosažitelných stavů
Je DKA ve kterém eliminujeme nedosažitelné stavy. To jsou ty stavy, do kterých se nedá z počátečního stavu dostat.
Minimální/redukovaný DKA (MDKA)
Je DKA bez nedosažitelných stavů ve kterém nejsou žádné 2 stavy nerozlišitelné:
Redukujeme nerozlišitelné stavy
Odstraníme přebytečné stavy (stavy nemající vliv na přijímání vstupního řetězce)
V minimálním DKA jsou stavy množiny stavů z původního automatu, pričemž v každé množině jsou stavy navzájem nerozlišitelné (jde v podstatě o třídy ekvivalence vzhledem k relaci nerozlíšitelnosti).
Odstranění nedosažitelných stavů
Převod DKA (Q, Σ, δ, q₀, F) na DKA bez nedosažitelných stavů (Q′, Σ, δ′, q₀, F′)
Najdeme všechny dostupné stavy Qᵢ
i = 0
Q₀ = {q₀} (tj. v nultém kroku je dostupný pouze počáteční stav)
repeat
Qᵢ₊₁ = Qᵢ ∪ {q | ∃ p ∈ Qᵢ ∃ a ∈ Σ: δ(p, a) = q} (tj. do množiny dostupných stavů přidáme všechny stavy do kterých se dá libovolným symbolem přejít z některého dostupného stavu z minulého kroku)
i++ (tj. přejdeme k dalšímu kroku)
until Qᵢ = Qᵢ₋₁ (tj. končíme pokud se nám v posledním kroku množina dostupných stavů nezměnila)
Nový automat sestavíme jako:
Q′ = Qᵢ tj. použijeme pouze dosažitelné stavy
Použijeme pouze přechody obsahující dosažitelné stavy
Použijeme pouze koncové stavy z množiny dosažitelných stavů (F′ = F ∩ Qᵢ)
Minimalizace KA
Převod DKA (Q, Σ, δ, q₀, F) na MDKA (Q′, Σ, δ′, q₀′, F′):
Převedeme na DKA bez nedostupných stavů
Určíme relaci nerozlišitelnosti stavů (≡ⁱ)
i = 0
≡⁰ = {(p, q) | p ∈ F ⇔ q ∈ F} (tj. na začátku rozlišujeme pouze dvě třídy – koncové a nekoncová stavy)
repeat
i++
until ≡ⁱ = ≡ⁱ⁻¹ (tj. končíme pokud v posledním kroku nedošlo k žádným změnám tříd ekvivalence)
Sestavíme nový automat jako:
Q′ = Q \ ≡ⁱ (tj. nové stavy odpovídají třídám ekvivalence původních stavů podle relace nerozlišitelnosti)
∀ p, q ∈ Q ∀ a ∈ Σ: δ′([p], a) = [q] ⇔ δ(p, a) = q (tj. nové přechody jsou mezi těmi třídami ekvivalence u ktrých existuje alespoň jeden odpovídající přechod mezi některými jejich prvky)
q₀′ = [q₀] (tj. počáteční stav je ta třída ekvivalence, která obsahuje původní počáteční stav)
F′ = {[q] | q ∈ F} (tj. koncové stavy jsou ty třídy ekvivalence, která obsahují některý z původních koncových stavů)
Převod NKA na DKA
Převod NKA (Q, Σ, δ, q₀, F) na DKA (Q′, Σ, δ′, q₀′, F′):
Q′ = (2Q \ {∅}) ∪ {nedef} (tj. nové stavy označujeme jako množiny původních stavů, místo prázdné množiny máme spec. stav {nedef})
Pro všechna S ∈ 2Q \ {∅} a pro všechna a ∈ Σpolož:
δ′(S, a) = ∪ δ(q, a) pro q ∈ S
Je-li δ′(S, a) = {∅} polož δ′(S, a) = nedef
Tj. pro všechny možné stavy S DKA a všechny možné znaky a na vstupu určíme následující stav jako sjednocení všech stavů do kterých vedou přechody se znakem a ze stavů v množině S. Pokud žádné takové přechody neexistují je přechod nedefinovaný.
F′ = {S, S ∈ 2Q ∧ S ∩ F ≠ ∅} (tj. za koncové stavy DKA považujeme všechny stavy jejichž množina obsahuje alespoň jeden koncový stav z NKA)
Konstrukce NKA k pravé regulární gramatice
Gramatika G = (N, Σ, P, S) na NKA (Q, Σ, δ, q₀, F)
Q = N ∪ {qF} (stavy NKA odpovídají nonterminálům gramatiky s přidaným qF)
Σ = Σ (tj. vstupní abeceda a množina terminálů jsou stejné)
q₀ = S (tj. počáteční stav odpovídá počátečnímu nonterminálu gramatiky)
Je-li S → ε pravidlo z P pak F = {S, qF} jinak F = {qF} (tj. koncové stavy jsou qF a v případě, že v gramatice je i prázdný řetězec tak i S)
Funkci přechodů definujeme:
Je-li A → aB pravidlo z P, pak δ(A, a) obsahuje B
Je-li A → a pravidlo z P, pak δ(A, a) obsahuje qF
Konstrukce NKA k levé regulární gramatice
Gramatika G = (N, Σ, P, S) na NKA (Q, Σ, δ, q₀, F)
Q = N ∪ {q₀} (stavy NKA odpovídají nonterminálům gramatiky s přidaným q₀)
Σ = Σ (tj. vstupní abeceda a množina terminálů jsou stejné)
q₀ = S (tj. počáteční stav odpovídá počátečnímu nonterminálu gramatiky)
Je-li S → ε pravidlo z P pak F = {S, q₀} jinak F = {S} (tj. koncové stavy jsou S a v případě, že v gramatice je i prázdný řetězec tak i q₀)
Funkci přechodů definujeme:
Je-li A → Ba pravidlo z P, pak δ(B, a) obsahuje A
Je-li A → a pravidlo z P, pak δ(q₀, a) obsahuje A
MyHill-Nerodova věta
Relace ~L:
Relace ~:
Notes
1. Otazka (predmet) (okruh): 13. Konečné automaty (TIN)
Kdo me primarne zkousel: Kočí Radek, Ing., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Tak ze začátku jsem se zeptal čím mám tedy začít. Tak, že prý formální definicí automatu. Začal jsem psát na tabuli definici a u toho ji popisoval slovně a pak už to začalo formou otázka a odpověď. Řek bych, že úplně ideální formát. Měl jsem něco říct o přechodové funkci a zapsat ji (měl jsem tam chybu, že jsem dal sjednocení místo kartézského součinu, na to mě upozornil, že s emu něco nezdá, tak jsem to hned opravil). Potom jak by vypadala kdyby se jednalo o deterministický konečný automat. Potom se ptal jaké jazyky přijímá jazyky a pak po mě chtěl něco, ale já nevěděl co 
 asi nějaký základní pojem ohledně přechodové funkce a co to znamená, když přijímá jazyk. Nakonec se zeptal co to je minimální automat a jaký je princip ho dosáhnout, řekl jsem jen odstranění nedostupných stavů a pak se snažil nějak popsat rozlišitelnost stavů, jen slovně, žádné formality. Doplňkové otázky žádné, fakt luxusní otázka i přístup zkoušejícího. Výsledná za B.
From <[link]> 
1. Otazka (predmet) (okruh): 19. Konečné automaty
Kdo me primarne zkousel: Meduna Alexander, prof. RNDr., CSc.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal netradičně s úkolem nakreslit automat přijímající řetezce nad binární abecedou, které obsahují alespoň jednu jedničku - nakreslil jsem jednoduchý dvou stavový DKA. Navrhl úpravu, která z toho automatu udělala NKA a zeptal se jak se automat změnil (řekl jsem, že se stal nedeterministickým) a jestli jsou ekvivalentní plus co to znamená - vysvětlil jsem, že musí příjmat stejný jazyk, pak jsem nahlas popřemýšlel a shodli jsme se, že jsou ekvivalentní. Dále chtěl popsat co je vlatně KA (stačilo slovně, ale 5-tici jsem stejně napsal) a nakonec jsem měl na tabuli formálně definovat přechodovou funkci pro deterministický KA (zdůraznil, že myslí DKA). Celou otázku jsme stihli velmi rychle a ještě před budíkem to ukončil s tím, že mu to stačí - A.
From <[link]> 
1. Otazka (předmět) (okruh): 13. Konečné automaty - varianty, minimalizace
Kdo me primarne zkousel: doc. Kolář
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Popsal jsem přechodová pravidla pro různé varianty KA, pak jsem se nějak zmínil o relaci nerozlišitelnosti a přešlo se na tu minimalizaci. 
From <[link]> 
1. Otazka (předmět) (okruh): TIN - Konecne automaty
Kdo me primarne zkousel: profesor Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Definoval jsem KA. Chtel popsat funkci prechodu, popsal jsem ji a ukazal rozdil mezi deterministickych a nedeterministickym. Rekl mi priklad retezce, mel jsem k nemu nadefinovat KA. Ten jsem nadefinoval, ale prvne jsem presne nepochopil jak to bylo mysleno, tak me posleze vyzval, ze tak to nebude. Chvili jsem premyslel, KA zmenil a to bylo spravne. Pohoda otazka, A 
.
From <[link]> 
1. Otazka (předmět) (okruh): 13) Konečné automaty
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Lepší otázku jsem si nemohl přát. Chtěl základní definici, trochu jsem zaváhal u funkce přechodu, zapomněl jsem na epsilon. Pak chtěl ať mu nakreslím graf automatu, který přijímá identifikátor, který nemusí začínat znakem, ale minimálně jeden znak obsahuje. Trvalo mi dost dlouho, než jsem pochopil co po mě vůbec chce, ale nakonec jsem ho nakreslil dobře.
From <[link]> 
1. Otazka (předmět) (okruh): 13 - TIN - Konecne automaty
Kdo me primarne zkousel: Smrz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
Chcel len absolutne elementarne veci. Nic formalne len ako co nakreslim. Ako som bol nervozny zvladol som si pomylit prienik so zjednotenim. Hned napovedal ze robim blbost a Holik prikyvoval. Ostatnych ludi z komisie to moc nebralo. Skoncil som tesne po zazvoneni budiku.
Znamka B.
From <[link]> 
1. Otazka (předmět) (okruh): 13. Konečné automaty (jazyky přijímané jazyky KA, varianty KA, minimalizace KA)
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
Tak to jsem si snad ani nezasloužil - 2 jednoduchý otázky od 2 pohodových zkoušejících, kteří chtěli jen naprostý základy. Měl jsem napsat formální definici KA, popsat přechodovou funkci a nakreslit jednoduchej automat přijímající řetězec s alespoň jedním numerických znakem, pak povinnou tečkou a zase aspoň jedním numerickým znakem. Samozřejmě jsem při tom udělal lehčí chybu na kterou mě upozornil Zbořil, opravil jsem, zazvonil budík a Meduna to hned ukončil. Známka B.
From <[link]> 
1. Otazka (předmět) (okruh): 13 TIN - Konečné automaty
Kdo me primarne zkousel: Holík
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
U KA chtěl vědět pouze přechodovou funkci NKA. Pak se zeptal co je 2^Q. Hned potom chtěl vědět převod regulárních výrazů na konečné automaty (nakreslit jak bych převedl jednotlivé části). Nakonec se zeptal, jestli bych věděl o čem je Myhil.Nerodova věta - což jsem už nevěděl, ale věděl jsem že na F to rozhodně není, tak mi to bylo docela jedno 
.
From <[link]> 
1. Otazka (předmět) (okruh): Konečné automaty, typy, minimalizace
Citace:
Kdo me primarne zkousel: Holub
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Definoval jsem automat, rozdíly, minimalizaci. Pak padla otázka na ekvivalenci NKA a důkaz. To mi pomohl 
From <[link]> 
1. Otazka (předmět) (okruh): Konečné automaty (TIN)
Kdo me primarne zkousel: Meduna Alexander, prof. RNDr., CSc.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Ze začátku jsem napsal definici automatu. Poté se mě zeptal co dělají automaty, řekl jsem že přijímají jazyky a pak chtěl matematickou definici toho, že automat přijímá jazyk. To jsem po několika (poměrně dost) nápovědách nakonec napsal (spíše tréma, než nevědomost). 
From <[link]> 
2. Otazka (předmět) (okruh): TIN 13. Konečné automaty (jazyky přijímané jazyky KA, varianty KA).
Kdo me primarne zkousel: Kolář
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Hneď mi povedal, že si mám vziať fixku a písať na tabuľu. Definoval som KA, RKA a DKA. Uviedol som aj ekvivalenciu KA a DKA. Kolář chcel vedieť jazyk prijímaný KA. Ten som definoval a potom sa zahral na neznalého a nevedel čo znamenjú tie 2 "paličky" s * 
 . Takže som ešte uviedol prechod a vysvetlil konfiguráciu. Ďalšie otázky nemal. Celkové hodnotenie ústnej za B.
Celkova znamka ze statni zaverecne zkousky: C
From <[link]> 
1. Otazka (předmět) (okruh): TIN Konecne automaty (determinismus x nedeterminismus, prevod RV na KA)
Kdo me primarne zkousel: Holik
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Zacal jsem definici KA ze je to petice atd. hned na to se me pan Holik zeptal jaky je rozdil mezi DKA a NKA. Rekl jsem neco ve smyslu, ze z DKA lze prejit do dalsiho stavu pomoci jedineho prechodu a u NKA ze lze pomoci jednoho prechodu prejit do vice ruznych stavu. Pak jsem dostal otazku jak udelam komplement DKA a jak bych udelal komplement NKA. Rekl jsem zebych ho nejdriv prevedl na DKA a az pak prohodil stavy. Nakonec se me zeptal na to jak prevedu RV na KA. Neco jsem tam splacal ale udelal jsem celkem hodne chyb. Posledni otazka od pana Holika byla jakou ma prevod RV na KA slozitost (to jsem netusil). Doplnujici otazku mi dal pan Koci jak to je s vyjadrovaci silou NKA a DKA coz jsem rekl ze jsou ekvivalentni. Konecna znamka za C.
From <[link]> 
1. Otazka (předmět) (okruh): TIN - 13. Konečné automaty
Kdo me primarne zkousel: jen Rogalewicz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Tak jsem začal "konečný automat je pětice..." a Rogalewicz se zaškaredil, že teda je to výpočetní model v prvé řadě a že ho můžeme reprezentovat pěticí. Chtěl ji teda odvykládat, já jestli ji můžu na tabuli napsat, to se mu moc nechtělo, nakonec jsem teda začal psát. Hned u psaní mi nenechal chvíli oddechu a ať to rovnou ale říkám, co to píšu. Řekl jsem, že to popíšu, až to dopíšu. Dopsal jsem, řekl jsem co je to Q a sigma, to ho moc nezajímalo, chtěl přechodovou funkci napsat, vysvětlit, co znamená teda to 2^Q. Nějak se mu nezdálo, když jsem mu to vysvětlil, že to je zobrazení na libovolnou podmnožinu -> "Ten automat si teda může vybrat sám, kam přejde?" Na to jsem řekl, že nedeterministický ano, vypadal, že neee, ale správně to bylo, tak nevím, co se mu nezdálo 
 Pak jak by vypadala fce přechodu pro DKA (jen to Q, ani ho nezajímalo, že by tam asi mělo být sjednocení s {nedef.}, to tak nějak odkýval, že joo, ale že ho to nezajímá). Tím to haslo, pak řekl, že máme abecedu a, b a chce nakreslit automat, který přijme jazyk, kde v řetězci je víc "a" než "b". Trochu to řekl nesrozumitelně, tak jsem se ještě ujišťoval jak to teda myslí, nakonec z něj vypadlo, že chce jazyk, kde jsou alespoň 3 "a" a libovolný počet "b". Tak jsem smazal dosavadní výtvor 
 a začal kreslit znovu, chvíli to trvalo, ale je to intuitivní, takže bez problémů. Jen jsem s koncovém stavu zapomněl, že můžu načítat pořád další a/b. Jen mi řekl, že mi tam něco chybí, po dokreslení řekl, že mu to stačí. Pohodička. Žádné převody NKA=>DKA, rozšířený KA, nic takového. Shrnutí: Vlastně jsem jen nadefinoval KA, funkci přechodu a nakreslil jeden DKA pro daný jazyk. Tím to skončilo.
From <[link]> 
2. Otazka (předmět) (okruh): 13. Konečné automaty (TIN)
(na papirku pouze "Konečné automaty")
Kdo me primarne zkousel: Hladká Eva, doc. RNDr., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Zadefinoval jsem automat M={...}. Pak chtela nakreslit nejaky priklad a zeptala se jaky to je automat. Nevedel jsem co mysli, tak rekla mame deterministicky a ... a to uz jsem se chytl a rekl, ze tohle je deterministicky. Tak at udelam nedeter -> udelal jsem. Na zaklade ceho je nedeter -> mel jsem dva prechody pres stejny symbol z jednoho stavu. A jak bych ho prevedl na deter. Zacal jsem vysvetlovat algoritmus a dostal jsem se jenom, ze se vytvari nove pseudo-stavy to ji stacilo. Co ma vetsi vyjadrovaci silu ne - deter. Vztah s regularnimi jazyky - stejna vyjadrovaci sila. To ze ji staci. Na to se jeste Krivka zeptal, ze tu pred chvili kolega popisoval jazyk a^n b^n a... tak jsem ho prerusil a hned mu rekl, ze to neni regularni jazyk, protoze bychom potrebovali zasobnik na pocitani znaku. A jak bych to dokazal - pumping lemma. Nechtel ani neformalne slyset jak zni. Ale jeho otazky uz byly tusim po budiku.
From <[link]> 
1. Otazka (předmět) (okruh): Konečné automaty 
Kdo me primarne zkousel: Rogalewicz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Měl jsem se zaměřit na nedeterministický a deterministický. Takže klasika pětice a pak přechod pro NKA a DKA. Trochu o uzávěrových vlastnostech, jak bych udělal doplněk, což jsem ale nevěděl. Pak minimalizace - co to je a k čemu. Teochu jsem to motal, ale to důležité jsem řekl, takže jsem neměl strach. Nakonec za E.
From <[link]> 
1. Otazka (okruh): 13. Konečné automaty.
Kdo me primarne zkousel: Jen Burget
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Zkoušel jen základ. Pohodička. Napsal jsem definici na tabuli, za chvilu hned zvonek. Jeste par dotazu na determinismus. Co ma vetsi vypočetní silu.
From <[link]> 
1. Otazka (okruh): 13. Konečné automaty (jazyky přijímané jazyky KA, varianty KA, minimalizace KA).
Kdo me primarne zkousel: Chudá začala pak pokračoval Vojnar
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Ze začátku to šlo, ale potom se přešlo na varianty KA a při postupu převodu na DKA jsem udělal pár chyb, kterých se chytnul Vojnar a chtěl to přesně i vyjádřením s jaké množiny na jakou množinu stavů se to převede. Pak ještě Vojnar prohlásil, že to mám hodně nahnuté tak ať vysvětlím minimalizaci to už jsem byl tak vykolejený že jsme tam cosik zkomolil, ale asi jsem jim řekl to co bylo potřeba, protože mi nakonec dali E. 
From <[link]> 
2. Otazka (předmět) (okruh): Konecne automaty. DKA vs NKA (TIN) (13)
Kdo me primarne zkousel: Rogalewicz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Napisal som zakladnu definiciu, povedal, co je co. Nakoniec sa opytal ako je to s vyjadrovacou silou. Na co chcel rozdiel v prechodovej funckii, co som trochu poplietol, ale dopracovali sme sa k vysledku.
From <[link]> 
1. Otazka (předmět) (okruh): Konečné automaty (jazyky přijímané jazyky KA, varianty KA, minimalizace KA).
Kdo me primarne zkousel: Rychlý Marek, RNDr., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Jednoduchá otázka - trochu jsem se zamotal do relace přechodu z jedné konfigurace do druhé - jinak bez větších problémů. Ještě se mě ptal u rozlišitelných stavů, jaká matematická vlastnost mě zde napadá. Vybavila se mi relace ekvivalence, jenže jsem si nebyl na sto procent jistý, tak jsem to raději neřekl...
From <[link]> 
1. Otazka (okruh): Konečné automaty
Kdo me primarne zkousel: Rogalewicz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Řekl jsem definici konečného automatu, deterministického i nedeterministického, tak se mě hned zeptal na vztah mezi nimi. Řekl jsem mu že jsou ekvivalentní a že je lze převést a jen stručně princip převodu NKA na DKA. Pak se ještě zeptal, k čemu jsou regulární jazyky uzavřené, tak jsem si vzpomněl na průnik, sjednocení a doplněk. Chtěl vysvětlit proč je uzavřený pro sjednocení, ale jak jsem začal říkat, že lze sestrojit nedeterministický rozšířený automat, z jehož počátečního stavu... tak mě přerušil že už mu to stačí.
From <[link]> 
1. Otazka (okruh): Konecne automaty
Kdo me primarne zkousel: Holub
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Povedal som vsetko sam, spytal sa na konecne jazyky a vztah NKA a DKA a stacilo mu to. (A)
From <[link]> 
1. Otazka (okruh): Konečné automaty, varianty, minimalizace.
Kdo me primarne zkousel: Kolář
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Super otázka, jedna z těch vysněných. Bohužel jsem se hned na začátku trochu zamotal do definice DKA, kdy jsem místo Q pro množinu symbolů použil N pro množinu nonterminálů 
 Ale jinak v pohodě, nechal mě mluvit a když se mu něco nezdálo (občas jsem se přeřekl), tak se jen zeptal "teď jste řekl, že ...." a dal mi prostor se opravit. Ty 4 minuty uběhly strašně rychle, měl jsem definovaný DKA, NKA, RKA a už to pípalo. Chtěl po mě ještě minimalizaci KA, do toho jsem se trochu zamotal, ale nakonec jsme to dali dohromady. Výsledek C.
From <[link]> 
1. Otazka (okruh): Konečné automaty(definice, přijímání jazyka, minimalizace)
Kdo me primarne zkousel: Havlice (externista)
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Napsal jsem formální definici NKA a vysvětloval jsem co která množina znamená. Pak se měl ptal na to jak automat přijímá jazyk, jestli může mít 0 stavů a jak se provádí determinizace. Dale se ptal jaký je rozdil v přijímaní jazyka deterministickými a nedeterministickými KA a proč jsou lepší ty nedeterministické. K čemu se automaty používájí v praxi.
From <[link]> 
1. Otazka (okruh): 13, TIN, konecne automaty
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Nieco som povedal, doost som sa motal, panika jak svina. Vzdy ma kludne opravil/nechal ma opravit, ked som to zblbol, nebol som si isty absolutne nicim, co bolo dane hlavne druhou otazkou, ktoru som si vobec nevedel vybavit, takze som bol v panike uz od zaciatku. Este, ze tie otazky nedavaju uz pred obhajobou DP. Meduna pomahal, obcas uz aj zacal za mna, ked som to zmrvil, bol skvely.
From <[link]> 
1. Otazka (okruh): Konečné automaty
Kdo me primarne zkousel: Rybička
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
Krásná otázka. Prakticky monolog až do zazvonění, pak dvě doplňující otázky (determinizace a minimalizace, jen myšlenka) a konec.
From <[link]> 