Gramatiky a automaty

Formální jazyky

Abychom mohli exaktně popsat, jak fungují počítačové programy, překladače nebo automaty, musíme si nejdříve vybudovat matematický aparát. Začneme od toho úplně nejmenšího elementu a postupným vrstvením dojdeme až k pojmu formálního jazyka. Na úplném začátku všeho stojí abeceda Jedná se o konečnou množinu symbolů (písmena, čísla nebo jiné znaky), ze kterých můžeme pomocí zřetězení skládat slova (řetězce).

Nyní uděláme myšlenkový skok. Co kdybychom vzali naši abecedu \(\Sigma\) a zkusili vypsat úplně všechna možná slova, která z ní jdou poskládat? Vznikne nám nekonečně velká množina slov, které se říká uzávěr abecedy (neboli Kleeneho uzávěr) a značí se \(\Sigma^*\). Pokud máme \(\Sigma = \{a, b\}\), pak uzávěr vypadá takto:

Formální jazyk je libovolná podmnožina uzávěru \(\Sigma^*\) nad abecedou \(\Sigma\).

• Formální jazyk je soubor slov vytvořených z určité abecedy. Nezabýváme se větami, ale jen jednotlivými slovy.
• Jazyk obsahuje slova z abecedy, která si vybereme z možných kombinací symbolů. Může obsahovat všechny, žádná, nebo jen některá slova.
• Jazyk lze definovat slovně, nebo pomocí gramatiky.

Vzhledem k tomu, že jazyk je množina slov, můžeme s ním provádět tyto operace:

Protože jsou prvky jazyka slova (řetězce), můžeme s nimi provádět i následující operace:

Abecedy a slova

• Abeceda (\(\Sigma\)) je konečná množina symbolů, což mohou být písmena, čísla nebo jiné znaky. Abeceda musí obsahovat alespoň jeden prvek.
• Řetězec (slovo) je posloupnost symbolů z této abecedy.
• Délka řetězce (kolik má symbolů) se značí \(|\alpha|\).
• Prázdný řetězec neobsahuje žádné symboly a značí se \(\varepsilon\), jeho délka je 0.
• Počet výskytů určitého znaku (například a) v řetězci α se značí jako #a(α).
• Reverzní (opačné) slovo \(a^R\) je slovo, které vznikne, když zapíšeš symboly slova α v opačném pořadí. Říká se tomu také zrcadlový obraz.
  • Například, pokud \(\alpha = a_1...a_n\), pak \(\alpha^R = a_n...a_1\).
  • Když obrátíš reverzní slovo zpět, dostaneš původní slovo: \((\alpha^R)^R = \alpha\).
  • Pro prázdný řetězec ε platí, že jeho reverzní obraz je stále prázdný: \(\varepsilon^R = \varepsilon\).
• Podslovo \(\beta\) je část slova \(\alpha\). To znamená, že \(\beta\) se nachází někde uvnitř slova \(\alpha\).
  • Předpona (prefix) je podslovo na začátku slova \(\alpha\).
  • Přípona (sufix) je podslovo na konci slova \(\alpha\).

Řetězení

Zřetězení (neboli spojení či konkatenace) dvou řetězců je proces, kdy vezmeš jeden řetězec a připojíš k němu druhý. Například pro řetězce α a β spojíš oba za sebe a získáš nový řetězec.

Vlastnosti zřetězení

• Délka spojeného řetězce je součet délek obou původních řetězců.
  • \(|\alpha.\beta| = |\alpha| + |\beta|\)
• Spojením slova s prázdným slovem vznikne původní slovo
  • \(\alpha.\varepsilon = \varepsilon.\alpha = \alpha\)
• Jedno slovo můžeme \(n\) krát zopakovat za sebou. To nazýváme \(n\)-násobné zřetězení a označuje se jako \(\alpha^n\).
  • Například \((abc)^3\) = \((abc).(abc).(abc) = (abcabcabc)\).
  • Pro \(n = 0\) je výsledek prázdné slovo \(\alpha^0 = \varepsilon\)
• Řetězení slova je asociativní, to znamená, že nezáleží, co zřetězíme první a co druhý, ve výsledku je to stejný.
  • \(\alpha . \beta . \gamma = (\alpha . \beta) . \gamma = \alpha . (\beta . \gamma)\)
• Řetězení není komutativní. Jinak řečeno, záleží na pořadí spojovaných slov.
  • \(\alpha . \beta \not= \beta . \alpha\)

Uzávěr abecedy

• Uzávěr abecedy (\(\Sigma^*\)) je množina všech možných slov, které lze vytvořit z abecedy \(\Sigma\) (to jsou všechny možné kombinace jejích symbolů, včetně prázdného slova).
• Pozitivní uzávěr (\(\Sigma^+\)) je stejná věc jako "klasický" uzávěr, ale neobsahuje prázdné slovo.
• Uzávěry jsou všechny možné způsoby, jak můžeš spojit symboly z abecedy libovolněkrát.
  • Tím vznikne spočetná množina.
  • Spočetná množina je taková, jejíž prvky můžeš spočítat, jako přirozená čísla (1, 2, 3…).
  • Spočetná množina může být i nekonečná.

Gramatika

Gramatika je sada pravidel, která říká, jak můžeme vytvořit slova jazyka z určitého počátečního symbolu. Vytváření slov funguje tak, že začneme s počátečním symbolem a postupně na něj uplatňujeme pravidla, dokud nevytvoříme požadované slovo. Gramatiku \(G\) zapisujeme jako uspořádanou čtveřici \(G = (N, T, P, S)\), kde

• \(N\) je množina pomocných symbolů (neterminálů).
• \(T\) je množina konečných symbolů (terminálů).
• \(P\) je množina přepisovacích pravidel.
• \(S \in N\) je počáteční symbol, také znamý jako kořen gramatiky.

Konečné a pomocné symboly

• Konečné symboly (neboli terminály, terminální symboly) jsou symboly, které už nelze dále přepisovat. Konečná slova, která gramatika generuje, obsahují jen tyto symboly.
• Pomocné symboly (neboli neterminály, neterminální symboly) jsou symboly, které slouží k popisu struktury jazyka a dalšímu přepisu. Někdy se jim říká proměnné.

Přepisovací pravidla

Přepisovací pravidla jsou množinou zobrazení, která určují, jak měnit symboly ve slovech. Pravidlo, které vypadá jako \(\alpha \to \beta\), znamená: "symboly \(\alpha\) přepiš na symboly \(\beta\)".

• Levá strana pravidla (\(\alpha\)) může obsahovat libovolnou kombinaci symbolů, ale musí tam být alespoň jeden pomocný (neterminální) symbol.
• Pravá strana pravidla (\(\beta\)) může obsahovat terminální i neterminální symboly. nebo může být i prázdný.

Při odvozování nového slova postupně přepisujeme části slov předchozích. Vybereme část, která odpovídá levé straně nějakého pravidla, a nahradíme ji pravou stranou. Zbytek slova před i za výskytem levé strany (tzv. kontext) zůstává stejný.

• Tomuto nahrazení levé strany pravou stranu říkáme přímé přepsání a označujeme ho symbolem \(\Rightarrow\).
• Pokud můžeme udělat více těchto přímých přepsání zasebou, mluvíme prostě o přepsání a zapisujeme to jako \(w \overset{*}{\Rightarrow} z\).

Jazyk \(L(G)\) generovaný gramatikou \(G\) je množina všech slov (vět), které můžeme vytvořit z počátečního symbolu pomocí konečného počtu přepisů. Tím, že se jedná o věty, tak jsou složeny jen z konečných (terminálních) symbolů.

Chomského hiearchie gramatik

Chomského hierarchie je rozdělení formálních gramatik podle toho, jak složité jazyky dokážou generovat.

Gramatiky typu 0 (neomezené/frázové gramatiky)

Tyto gramatiky zahrnují všechny možné formální gramatiky. Generují jazyky, které mohou být rozpoznané Turingovým strojem, což jsou velmi obecné stroje schopné zpracovat širokou škálu problémů. Tyto jazyky se nazývají rekurzivně spočetné jazyky.

• Nejsou zde žádná omezení na tvar pravidel.
• Každé pravidlo má formu: \(\alpha \to \beta\).
• \(\alpha\) musí obsahovat alespoň jeden neterminál a může být jakýmkoli řetězcem terminálů a neterminálů.
• \(\beta\) může být libovolný řetězec terminálů a neterminálů.

Gramatiky typu 1 (kontextové gramatiky)

Tato gramatika generuje kontextové jazyky a je omezená tím, že žádné pravidlo nemůže zkracovat řetězce. Kontextové jazyky může rozpoznat Turingův stroj s omezenými zdroji (tzv. lineárně ohraničený).

• Pravidla musí dodržovat formu \(\alpha{X}\beta \to \alpha{\gamma}\beta\).
  • \(X\) je pomocný symbol (neterminál)
  • \(\alpha,\,\beta,\,\gamma\) jsou řetězce konečných a/nebo pomocných symbolů (\(\alpha,\,\beta,\,\gamma \in (T \cup N)^*\))
  • \(\gamma\) nesmí být prázdné slovo \(\varepsilon\).

• Alternativní, ale ekvivalentní, definice: \(\alpha \to \beta\)

  • \(\alpha \in (N \cup T)^* . N . (N \cup T)^*\)
  • \(|\alpha| \le |\beta|\)

• Pravidlo S → ε je povoleno jen, pokud se \(S\) nevyskytuje na pravé straně žádného jiného pravidla.

Gramatiky typu 2 (bezkontextové gramatiky)

Tyto gramatiky generují bezkontextové jazyky, které lze rozpoznat nedeterministickým zásobníkovým automatem.

• Pravidla musí dodržet formu \(X \to \gamma\) kde

  • \(X\) je pomocný symbol
  • \(\gamma\) je řetězec konečných a/nebo pomocných symbolů (\(\alpha,\,\beta,\,\gamma \in (T \cup N)^*\))

• Na levé straně může být pouze jeden pomocný symbol (není v kontextu).

Gramatiky typu 3 (regulární gramatiky)

Tyto gramatiky generují regulární jazyky, které jsou nejjednodušší a mohou být rozpoznané konečným automatem (automat bez paměti). U všech přepisovacích pravidel je na levé straně přesně jeden neterminál a na pravé straně nejvýše jeden neterminál.

• Gramatika může obsahovat pravidlo \(S \to \varepsilon\), pokud se \(S\) nevyskytuje v žádném jiném pravidle na pravé straně.

Regulární gramatika

Regulární gramatika má pravidla ve tvaru

• \(A \to aB\)
• \(A \to Ba\)
• \(A \to a\)
• \(A \to \varepsilon\)

Podle umístění terminálního symbolu se rozlišuje

• levá regulární gramatika: terminální symbol je na začátku pravé strany (\(A \to Ba\))
• pravá regulární gramatika terminální symbol je na konci pravé strany (\(A \to aB\))

Lineární gramatika

Do regulárních gramatik spadají také pravidla, která splňují podmínky lineární gramatiky. Lineární gramatika je obecnější definice regulární gramatiky, kdy terminály \(x\) a \(y\) nemusíme tahat přímo z množiny terminálů \(T\), ale z jejího uzávěru \(T^*\). Ten obsahuje kromě terminálů i jejich různé kombinace a opakování. Lineární gramatika splňující pravidla G3 má pravidla ve tvaru:

• \(A \to xB\) (pravá lineární gramatika)
• \(A \to By\) (levá lineární gramatika)
• \(A \to x\)
• \(A \to \varepsilon\)

Pokud narazíme na pravidlo typu \(A \to xBy\), nebo respektive \(A \to xB\) a \(B \to Cy\), pak se sice jedná o lineární gramatiku, ale splňující podmínky pro G2, ne pro G3. Lineární gramatika spadá do gramatiky typu 2, pokud se v přepisových pravidlech nachází jak levá, tak i pravá lineární gramatika. Jinak řečeno, existuje takové pravidle, které je zapsané nebo ho lze zapsat ve tvaru \(A \to xBy\).

Příklady

Konečný automat

Automat je abstraktní matematický stroj, který slouží k rozpoznávání formálních jazyků. Automat prochází slova a rozhoduje, jestli patří do daného jazyka. Automaty se klasifikují podle toho, jaké jazyky dokážou rozpoznat (např. regulární, bezkontextové jazyky). Konečný automat (KA) je abstraktní model, který simuluje určitý typ výpočtu. Místo čísel pracuje s symboly.

Podle účelu automatu

Rozpoznávací konečný automat (akceptor)

Tento typ automatu rozhoduje, zda dané vstupní slovo patří do určitého jazyka. Vydává jasnou odpověď typu ano/ne. Rozpoznávacím konečným automatem nazýváme každou pětici \(A = (Q, \Sigma, \delta, q_0, F)\), kde:

• \(Q\) je konečná neprázdná množina stavů
• \(\Sigma\) je vstupní abeceda
• \(\delta\) je přechodová funkce, která určuje, do jakého stavu automat přejde podle aktuálního stavu a přečteného symbolu.
• \(q_0 \in Q\) je počáteční stav
• \(F \in Q\) je konečná neprázdná množina koncových stavů, kde automat může skončit a rozhodnout, že slovo patří do jazyka.

Klasifikační konečný automat (klasifikátor)

Tento automat zařazuje vstupní řetězec do jedné z několika tříd. Rozpoznávací KA je speciálním případem klasifikačního KA, protože rozlišuje pouze mezi dvěma možnostmi (patří/nepatří). Klasifikačním konečným automatem nazýváme každou pětici \(A = (Q, \Sigma, \delta, q_0, \{Q_i\})\), kde:

• \(Q\) je konečná neprázdná množina stavů
• \(\Sigma\) je vstupní abeceda.
• \(\delta\) je přechodová funkce, která určuje, do jakého stavu automat přejde podle aktuálního stavu a přečteného symbolu.
• \(q_0 \in Q\) je počáteční stav.
• \(\{Q_i\}\) je rozklad množiny stavů \(Q\). Každý stav z Q patří právě do jedné skupiny (třídy) {Qi}. Skupiny jsou navzájem oddělené (disjunktní) a jejich sjednocením dostaneme celou množinu stavů Q.

Konečný automat s výstupní funkcí (translátor)

Tento typ automatu vytváří výstupní řetězec na základě vstupního řetězce.

Podle architektury automatu

Mealeyho typ

S výstupní funkcí Mealyho typu popisujeme uspořádanou šesticí \(A = (Q, \Sigma, O, \delta, \lambda, q_0)\), kde:

• \(Q\) je konečná neprázdná množina stavů.
• \(\Sigma\) je vstupní abeceda.
• \(O\) je konečná neprázdná množina výstupních symbolů.
• \(\delta\) je přechodová funkce, která určuje, do jakého stavu automat přejde podle aktuálního stavu a přečteného symbolu.
• \(\lambda\) je výstupní funkce, která určuje, jaký výstup se generuje na základě aktuálního stavu a vstupu.
• \(q_0 \in Q\) je počáteční stav.

Moorův typ

KA s výstupní funkcí Moorova typu popisujeme uspořádanou šesticí \(A = (Q, \Sigma, O, \delta, \lambda, q_0)\), kde:

• \(Q\) je konečná neprázdná množina stavů.
• \(\Sigma\) je vstupní abeceda.
• \(O\) je konečná neprázdná množina výstupních symbolů.
• \(\delta\) je přechodová funkce, která určuje, do jakého stavu automat přejde pouze podle aktuálního stavu.
• \(\lambda\) je výstupní funkce, která určuje, jaký výstup se generuje na základě aktuálního stavu.
• \(q_0 \in Q\) je počáteční stav.

Převod mezi Moore a Mealey

Podle determinismu automatu

Tato osa rozdělení neříká, k čemu automat slouží, ale jakým způsobem se rozhoduje, když čte vstupní symbol. Určuje, zda je cesta výpočtu jednoznačná, nebo zda se může větvit.

Deterministický konečný automat (DKA)

Deterministický automat je přímočarý. V každém okamžiku výpočtu je jednoznačně dáno, co se stane v následujícím kroku. Neexistuje žádný prostor pro náhodu nebo pochybnosti.

Formálně je DKA (akceptor) uspořádaná pětice \(A = (Q, \Sigma, \delta, q_0, F)\), kde klíčovou roli hraje přechodová funkce \(\delta\): $\(\delta: Q \times \Sigma \to Q\)$

Nedeterministický konečný automat (NKA)

Nedeterministický automat přináší do výpočtu prvek „paralelismu“ nebo „hádání“. Ze stejného stavu může pro jeden symbol existovat více možných přechodů, nebo naopak žádný.

Formálně je NKA uspořádaná pětice \(A = (Q, \Sigma, \delta, I, F)\), kde si všimni dvou zásadních rozdílů oproti DKA: 1. Množina počátečních stavů \(I \subseteq Q\): Automat může začínat ve více stavech současně. 2. Přechodová funkce \(\delta\) vrací množinu stavů: $\(\delta: Q \times \Sigma \to \mathcal{P}(Q)\)$ (Zápis \(\mathcal{P}(Q)\) neboli \(2^Q\) značí potenční množinu – množinu všech podmnožin stavů \(Q\). Výsledkem přechodu je tedy celá skupina stavů, klidně i prázdná množina \(\emptyset\).)

Převod mezi NKA a DKA

Základním teoretickým poznatkem je, že NKA a DKA jsou ekvivalentní. Nedeterminismus nepřidává automatu žádnou výpočetní sílu navíc (oba modely rozpoznávají stejnou třídu regulárních jazyků \(L_3\)).

Každý nedeterministický automat lze systematicky převést na deterministický pomocí algoritmu zvaného podmnožinová konstrukce. Nedeterminismus v NKA znamená, že z jednoho stavu vede pro stejný symbol více šipek do různých stavů (automat má na výběr a musí paralelně „hádat“ cestu).

Konstrukce gramatiky z konečného automatu

Při návrhu gramatiky pro konečný automat vycházíme z faktu, že konečné automaty jsou ekvivalentní regulárním gramatikám (v Chomského hierarchii jde o jazyky typu 3). Chceme-li sestavit gramatiku, která bude generovat stejný jazyk, jaký přijímá konečný automat, musíme vytvořit tzv. pravou regulární gramatiku. V ní mají přepisovací pravidla striktně omezený tvar:

• \(A \to aB\)
• \(A \to a\)
• \(A \to \varepsilon\)

Zásobníkový automat

Zásobníkový automat je rozšíření konečného automatu, který má k dispozici nekonečný zásobník. Problémem regulárních jazyků, které rozpoznává konečný automat, je fakt, že nemá žádnou formu paměti a uchovává si pouze aktuální stav. To dělá problém v situaci, kdy na pravé straně přepisovacího pravidla existují pouze neterminály. Vzniká tím totiž rekurze, se kterou si konečný automat nedokáže poradit. Z definice takový stavu u regulární gramatiky není možný, protože na pravé straně musí být vždycky alespoň jeden terminál. U bezkontextové je ale pravá strana libovolný řetězec symbolů z úzávěru sjednocení terminálů a neterminálů.

Přidaný zásobník vytváří novou formu vstupu a výstupu. Automat čte kromě vstupního slova také stav zásobníku, a může si do zásobníku zapsat symbol. Může se tak do jisté míry nekonečně vracet a zpracovávat nekonečně dlouhé slovo neustálým zapisováním a čtením zásobníku. U zásobníkového automatu může konečný stav nastat tím, že dojde do koncového stavu, nebo že bude na konci čtení zásobník prázdný.

Turingův stroj

Turingův stroj je teoretický model počítače, který se používá pro modelování algoritmů. Turingova teze říká, že ke každému algoritmu existuje ekvivalentní TS (mohou ale existovat algoritmicky nerozhodnutelné problémy). Turingův stroj je forma konečného automatu, který čte a zapisuje na nekonečnou pásku v obou směrech. Počáteční stav nesmí být shodný s koncovým stavem.

Varianty Turingova stroje:

• Nekonečná jenom směrem doprava (pravostranně nekonečný)
• Lineárně ohraničený
• Vícepáskový (má vstupní, výstupní a pracovní pásky)
• Vícehlavový
• TS s lineární páskou či páskami
• TS s nelineární páskou či páskami

Rozhodnutelnost

Rozhodnutelnost je vlastnost hromadného problému, která říká, jestli pro tento problém existuje algoritmus (počítačový program), který dokáže v konečném čase pro libovolný vstup rozhodnout, zda pro něj platí určité tvrzení či nikoliv.

Problém zastavení

Problém zastavení Turingova stroje je algoritmicky nerozhodnutelný problém, který říká, že neexistuje obecný algoritmus, který by pro všechny vstupy všech programů dokázal určit, jestli se program zastaví, nebo poběží navždy.

Postův korespondenční problém

Postův korespondenční problém je nerozhodnutelný problém, který má jednoduché zadání: máme dvojice slov, přičemž ke každé dvojici máme nekonečně mnoho kopií. Je možné najít sekvenci dvojic, u kterých jsou první slova stejná a druhá slova stejná? Takový algoritmus, který by určil existenci řešení, neexistuje.

Problém zániku matic 3x3

Problém zániku matic je nerozhodnutelný problém, který se soustředí kolem čtvercových matic 3x3. Cílem je rozhodnout, jestli lze libovolně dlouhým součinem získat nulovou matici.

• Pro matici \(1\times1\) (skalár) je problém triviální, stačí vynásobit nulou.
• Pro matici \(2\times2\) je problém otevřený a čeká se na jeho vyřešení.
• Pro matici \(3\times3\) je problém nerozhodnutelný.

Překladače

Překladač je program, který převádí kód zapsaný v jednom jazyce do kódu zapsaného v jiném jazyce se zachováním sémantického významu. Překladače se dělí na dvě části:

• na frontend, který překládá výchozí jazyk do intermediálního jazyka
• a na backend, který překládá intermediální jazyk do cílového jazyka