🤖 BI-AAG – Automaty a gramatiky

📚 Základní pojmy – abeceda, řetězec, jazyk

Řetězec nad Σ je konečná posloupnost symbolů. Prázdný řetězec = ε.

• Σ* – množina všech řetězců nad Σ (včetně ε)
• Σ+ – množina všech neprázdných řetězců; Σ* = Σ+ ∪ {ε}
• Zřetězení: asociativní, není komutativní; ε je neutrální prvek
• Reverze: xR obrátí pořadí symbolů; (abcd)R = dcba
• Délka: |x| ≥ 0; |ε| = 0

Kleeneho iterace: L* = L0 ∪ L1 ∪ L2 ∪ ... kde L0 = {ε}. Vždy platí ε ∈ L*.

🏛️ Chomského hierarchie

Gramatika G = (N, Σ, P, S) kde N jsou neterminály, Σ terminály (N∩Σ=∅), P pravidla, S počáteční symbol.

Hierarchie jazyků: Regulární ⊂ Bezkontextové ⊂ Kontextové ⊂ Rekurzivně spočetné.

⚙️ Deterministický konečný automat (DKA)

Jak funguje? DKA čte vstupní řetězec symbol po symbolu. Pro každý symbol a v každém stavu je přesně jeden přechod (deterministický). Řetězec je přijat, pokud po přečtení celého vstupu skončí v koncovém stavu.

Konfigurace: dvojice (q, w) ∈ Q × Σ* kde q je aktuální stav, w je dosud nepřečtený vstup.

Přechod: (q, aw') ⊢ (p, w') pokud δ(q, a) = p

Přijímaný jazyk: L(M) = {w : (q0, w) ⊢* (q, ε), q∈F}

🔀 Nedeterministický konečný automat (NKA)

Klíčový rozdíl DKA vs NKA:

• DKA: z každého stavu vede pro každý symbol přesně 1 přechod
• NKA: z každého stavu může vést pro jeden symbol 0, 1 nebo více přechodů
• Řetězec přijímán NKA = existuje alespoň jedna akceptující posloupnost přechodů

ε-přechody: NKA může provést přechod bez čtení vstupního symbolu. Funkce ε-Closure(q) vrací všechny stavy dosažitelné z q pomocí ε-přechodů.

Věta: Ke každému NKA existuje ekvivalentní DKA (přijímají stejný jazyk). NKA jsou tedy stejně silné jako DKA – oba rozpoznávají právě regulární jazyky.

🔄 Determinizace NKA → DKA (podmnožinová konstrukce)

Postup:

1. Počáteční stav DKA = {q0}
2. Pro každý stav DKA (= množinu stavů NKA) q' a každý symbol a: δ'(q', a) = ∪_{p∈q'} δ(p, a)
3. Nové stavy přidáváme dokud existují neprozkoumané
4. Koncové stavy DKA = stavy obsahující alespoň jeden koncový stav NKA

Proč to funguje? NKA v každém okamžiku může být v několika stavech najednou. DKA to simuluje tak, že si pamatuje celou množinu možných aktuálních stavů. Tato množina je vždy jednoznačně určena přečteným prefixem vstupního slova.

🗺️ Dosažitelné a užitečné stavy

Dosažitelný stav: stav q je dosažitelný, pokud existuje w ∈ Σ* takové, že (q0, w) ⊢* (q, ε). Nedosažitelné stavy lze bezpečně odstranit (BFS/DFS od q0).

Užitečný stav: stav q je užitečný, pokud existuje w ∈ Σ* takové, že (q, w) ⊢* (f, ε) pro nějaký f∈F. Zbytečné stavy (ze kterých nelze dojít do koncového stavu) lze také odstranit (BFS/DFS od F zpětně).

📐 Minimalizace deterministického konečného automatu

Hopcraftův algoritmus (Myhill-Nerodova věta v praxi):

1. Inicializace: Rozděl stavy do dvou tříd: koncové QII = F a nekoncové QI = Q\F
2. Iterace: Pokud existují dva stavy ve stejné třídě, ale pro nějaký symbol a přecházejí do různých tříd, rozděl jejich třídu
3. Opakuj dokud se třídy nemění
4. Výsledek: Každá třída = jeden stav minimálního DKA

Na konci algoritmu musí platit: δm(Qi, a) = Qj ⟺ ∀q ∈ Qi: δ(q, a) ∈ Qj

🔧 Operace s konečnými automaty

Regulární jazyky jsou uzavřené na sjednocení, průnik, doplněk, zřetězení a iteraci.

📝 Regulární gramatiky

Převod regulární gramatiky na NKA:

• Stavy NKA = neterminály N ∪ {A} (A je nový akceptující stav)
• A → aB v G ⟹ δ(A, a) ∋ B v NKA
• A → a v G ⟹ δ(A, a) ∋ A_fin v NKA (přechod do akceptujícího stavu)
• Počáteční stav NKA = S

Převod NKA na regulární gramatiku:

• Neterminály = stavy NKA
• Pro každý přechod δ(B, a) ∋ C: pravidlo B → aC
• Pokud C∈F: také pravidlo B → a
• Pokud q0∈F: speciálně ošetřit (přidat S'→ε nebo S'→...)

🔤 Regulární výrazy

Jazyk regulárního výrazu:

• L(∅) = ∅, L(ε) = {ε}, L(a) = {a}
• L(x+y) = L(x) ∪ L(y)
• L(x.y) = L(x).L(y)
• L(x*) = (L(x))*

Algebraické vlastnosti:

• P4: x+x = x (idempotence sjednocení)
• P7: ∅.x = x.∅ = ∅ (∅ je nulový prvek pro zřetězení)
• V1: ∅* = ε
• V3: (x*)* = x*
• V4: (x+y)* = (x*y*)*
• V9: (xy)*x = x(yx)*

🔢 Regulární rovnice a převody mezi formalismy

KA → regulární výraz (metoda regulárních rovnic – odchozí přechody):

1. Pro každý stav q zapišeme rovnici: Xq = Σ_a Xp (pro každý přechod δ(q,a)=p)
2. Ke koncovým stavům přidáme + ε
3. Soustavu pravých regulárních rovnic vyřešíme (substitucí + Ardenovo lemma)
4. Výsledek = Xq0

Regulární výraz → NKA (Glushkova metoda – metoda sousedů):

1. Očísluj všechny výskyty symbolů ve výrazu: a1b2*a3 + a4c5
2. Zjisti Z (počáteční symboly), K (koncové symboly), P (dvojice sousedů)
3. Stavy = {q0} ∪ {ai}; přechody z q0 pro symboly z Z; přechody ai→bj pro každou dvojici aibj ∈ P
4. Koncové stavy = K ∪ {q0 pokud ε ∈ L(V)}

💪 Pumping lemma (PL) pro regulární jazyky

Intuice: Pokud slovo je dost dlouhé, automat musí navštívit jeden stav dvakrát ⟹ existuje smyčka ⟹ lze ji libovolně opakovat.

Použití PL k důkazu, že L není regulární:

1. Předpokládejme, že L je regulární ⟹ existuje p
2. Zvolíme konkrétní slovo w ∈ L s |w| ≥ p (typicky w = 0^p 1^p)
3. Ukážeme, že pro každé rozdělení w=xyz splňující |y|≥1 a |xy|≤p existuje k, pro které xy^k z ∉ L
4. To je spor s PL ⟹ L není regulární

Příklad: L = {0ⁿ1ⁿ : n≥1} není regulární. Vezmeme w = 0ᵖ1ᵖ. Podmínka |xy|≤p zaručuje, že y = 0^j pro j≥1. Pak xy⁰z = 0^(p-j)1^p ∉ L, spor.

🧮 Myhill-Nerodova věta

Praktické použití:

• Důkaz neregularity: ukážeme, že ~_L má nekonečně mnoho tříd. Např. pro {0ⁿ1ⁿ}: žádné dvě různé mocniny 0^i a 0^j (i≠j) nejsou ekvivalentní, protože 0^i 1^i ∈ L, ale 0^j 1^i ∉ L.
• Konstrukce minimálního DKA: Stavy = třídy ~_L. Počet stavů minimálního DKA = index ~_L (počet tříd).

🌳 Bezkontextové gramatiky (BG)

Klíčový rozdíl od regulárních: Pravá strana pravidla může obsahovat více neterminálů a ve složitém pořadí. To umožňuje popis rekurzivních struktur jako jsou závorky, vnořené bloky kódu apod.

Derivace: α ⇒ β (přímá derivace) pokud v α nahradíme jeden neterminál dle pravidla. α ⇒* β (libovolný počet kroků), α ⇒+ β (alespoň jeden krok).

Uzavřenost BJ: Třída bezkontextových jazyků je uzavřena na sjednocení, součin a iteraci. Není uzavřena na průnik a doplněk!

Praktické využití: BG popisují syntaxi programovacích jazyků (EBNF, BNF). Výrazy jako E → E+T | T zachycují precedenci operátorů.

⚖️ Jednoznačnost a nejednoznačnost gramatik

Klasický příklad – dangling else:

• S → if b then S else S | if b then S | a
• Věta if b then if b then a else a má dva derivační stromy
• Oprava: separovat S1 (může mít else) a S2 (nemůže mít else)

Proč záleží na jednoznačnosti? Při syntaktické analýze chceme mít jednoznačný derivační strom – určuje sémantiku programu (pořadí operací, vazby proměnných). Nejednoznačná gramatika neumožňuje deterministický parser.

🔧 Transformace bezkontextových gramatik

Zbytečné symboly:

• Negenerující neterminál: nelze z něj odvodit žádné terminální slovo. Algoritmus: BFS – neterminálem přidáváme do Nt ty, z jejichž pravé strany lze odvodit terminální slova. Odstraníme neterminály mimo Nt.
• Nedostupný symbol: nevyskytuje se v žádné větné formě. Algoritmus: BFS od S – přidáváme symboly dostupné z dosud přidaných.
• Zbytečný symbol = negenerující nebo nedostupný. Algoritmus: 1) odstraň negenerující, 2) odstraň nedostupné.

ε-pravidla: Algoritmus k jejich odstranění: 1) Najdi Nε – množinu neterminálů derivujících ε (BFS). 2) Pro každé pravidlo A → X1X2...Xn vytvoř všechny varianty, kde Xi∈Nε může být vynecháno. 3) Zachováme pravidlo S'→ε jen pokud ε∈L(G).

Jednoduchá pravidla A → B (A,B∈N): Algoritmus: Pro každé A najdi NA = {B : A⇒+B} (tranzitivní uzávěr). Pak pravidla A→α (α∉N) přidej i pro každý B∈NA.

📐 Chomského normální tvar (CNF)

Každý BJ lze generovat gramatikou v CNF. Postup převodu z vlastní gramatiky bez jednoduchých pravidel:

1. Pravidla A → BC a A → a necháme
2. Pravidla A → X1X2...Xk pro k>2: zavádíme pomocné neterminály Y a rozkládáme: A → X1' Y_X2..Xk, Y → X2' Y_X3..Xk, ...
3. Terminály v delších pravidlech: místo a přidáme neterminál a' s pravidlem a'→a

📊 Algoritmus Cocke-Younger-Kasami (CYK)

Postup:

1. Inicializace: P[i,1] = {A : A→xi ∈ P} pro každý symbol xi
2. Iterace (délka i od 2 do n, pozice j od 1 do n-i+1): P[j,i] ∪= {A : A→BC, B∈P[j,k], C∈P[j+k,i-k]} pro každé k∈{1,...,i-1}
3. Výsledek: x ∈ L(G) ⟺ S ∈ P[1,n]

📚 Zásobníkový automat (ZA)

Konfigurace ZA: trojice (q, w, α) kde q∈Q je stav, w∈Σ* je zbytek vstupu, α∈G* je obsah zásobníku (vrchol vlevo).

Přechod: (q, aw, αβ) ⊢ (p, w, γβ) pokud (p, γ) ∈ δ(q, a, α). ZA přečte symbol a, ze zásobníku odebere α a vloží γ.

Dvě varianty přijetí:

• Přechodem do koncového stavu: L(R) = {w : (q0, w, Z0) ⊢* (q, ε, γ), q∈F}
• S prázdným zásobníkem: Lε(R) = {w : (q0, w, Z0) ⊢* (q, ε, ε)}

Věta: Jazyk L je bezkontextový ⟺ L je přijímán zásobníkovým automatem.

🎯 Deterministický zásobníkový automat (DZA)

Klíčové omezení: DZA jsou slabší než NZA – přijímají vlastní podtřídu bezkontextových jazyků (deterministické bezkontextové jazyky). Například palindromy nepatří do deterministických BJ.

⬇️ Syntaktická analýza shora dolů (Top-Down, LL)

Konstrukace ZA pro SA shora dolů:

R = ({q}, Σ, N∪Σ, δ, q, S, ∅) kde:

• δ(q, ε, A) = {(q, α) : A→α ∈ P} pro každý A∈N (expanze)
• δ(q, a, a) = {(q, ε)} pro každý a∈Σ (srovnání)

Zásobník obsahuje dosud nevyřešenou část větné formy. Vrchol zásobníku je vlevo.

Problémy nedeterministické SA shora dolů: Pokud má neterminál více pravidel se stejným prvním symbolem na pravé straně, automat neví, které pravidlo použít ⟹ musí hádat (nedeterminismus).

LL(k) gramatiky (Deterministic Top-Down): ZA rozhoduje, které pravidlo použít, na základě aktuálního neterminálu na zásobníku a k dalších symbolů vstupu. LL analýza je obsahem předmětu BI-PJP.

⬆️ Syntaktická analýza zdola nahoru (Bottom-Up, LR)

Konstrukace ZA pro SA zdola nahoru:

R = ({q, r}, Σ, N∪Σ∪{#}, δ, q, #, {r}) kde:

• δ(q, a, ε) = {(q, a)} pro každý a∈Σ (přesun / shift)
• δ(q, ε, α) = {(q, A)} pro každé pravidlo A→α (redukce / reduce)
• δ(q, ε, #S) = {(r, ε)} (přijetí)

Vrchol zásobníku je vpravo. ZA přesouvá symboly ze vstupu na zásobník (shift), a když vrchol zásobníku odpovídá pravé straně pravidla, redukuje na levou stranu (reduce).

LR(k) gramatiky (Deterministic Bottom-Up): Rozhodnutí shift/reduce na základě zásobníku a k symbolů vstupu. Mnohem silnější třída než LL(k). LR analýza je obsahem předmětu NI-SYP.

🔗 Vztah BG a ZA – varianty zásobníkových automatů

Překlad výše na modely SA:

• SA shora dolů = ZA s expanzí neterminálů na zásobníku + srovnáváním symbolů (levá derivace)
• SA zdola nahoru = ZA s přesuny na zásobník a redukcemi (pravá derivace)

📋 Vlastnosti bezkontextových jazyků

Uzavřenost BJ:

Pumping lemma pro BJ: Nechť L je BJ. Pak ∃p≥1 takové, že každé w∈L s |w|≥p lze zapsat jako w = uvxyz kde |vy|≥1, |vxy|≤p, a ∀k≥0: uv^k xy^k z ∈ L. (Obě části v a y se pumpují souběžně.)