Úvod do formálnych jazykov

História

Model Turingovho stroja, skonštruovaný Mike Daveyom, vystavený na Harvardovej univerzite v roku 2012.

V 30-tych rokov 20. storočia britský matematik a logik Alan Turing skúmal abstraktné výpočtové zariadenie, ktoré malo všetky schopnosti dnešných počítačov. Takéto zariadenie sa nazýva Turingov stroj.

Otázkou bolo: dajú sa všetky problémy riešiť pomocou algoritmu?

O Turingovom stroji v kontexte formálnych jazykov a automatov hovoríme že je to "automat" - teda, zariadenie ktoré dokáže automaticky previesť nejaký vstup na výstup. Každý automat pritom využíva určité pravidlá, podľa ktorých generuje výstup - gramatiku.

Základné pojmy

Predtým, ako môžme pochopiť čo je presne automat a ako sa dá matematiky alebo schematicky vyjadriť jeho princíp fungovania, si musíme vysvetliť základné pojmy. Našťastie, veľa z týchto pojmov už poznáme pretože ich využívame v každodennom živote, a teda znamenajú presne to, čo si pod nimi predstavujeme. Ale možno z trochu iného hľadiska - toho matematického:

Abeceda

Abeceda je ľubovoľná konečná množina symbolov. Označujeme ju písmenom $V$. Napríklad: $V=\{a,b,c,d,\dots ,x,y,z\}$ je množina, ktorá obsahuje všetky malé písmená (symboly) anglickej abecedy.

Symboly nemusia byť iba písmená, ale aj číslice a dokonca iné špeciálne znaky. To znamená, že aj nasledujúca abeceda je platná: $V=\{-,\mathrm{\Psi },\mathrm{\Theta },\mathrm{\aleph },\mathrm{♡},⅁,\mathrm{♠}\}$.

Slovo

Slovo $w$ je ľubovoľná konečná postupnosť symbolov z abecedy $V$. Dĺžku slova $w$ (teda, počet znakov v slove) označujeme ako $|w|$. Napríklad:$$\begin{array}{lcl}w& =& mama\\ |w|& =& 4\end{array}$$

Prázdne slovo

Prázdne slovo označujeme gréckym písmenom $ϵ$ (Epsilon). Je to slovo, ktoré má nulovú dĺžku: $|ϵ|=0$. Predstav si to ako prázdny reťazec v programovacom jazyku: "" // reťazec nulovej dĺžky: je to nič. Aj keď sa na prvý pohľad zdá že to nedáva zmysel a tento symbol je nepotrebný, neskôr pri príkladoch zistíme, že spĺňa dôležitú funkciu pri popisovaní gramatík (pretože v istých situáciách potrebujeme vyjadriť to "nič").

Jazyk

Jazyk označujeme pomocou písmena $L$ (ako z anglického Language). Jedná sa o ľubovoľnú podmnožinu množiny $V^{*}$ všetkých slov nad nejakou abecedou $V$. To znamená, že ak $V^{*}$obsahuje všetky možné slová (kombinácie symbolov) z abecedy $V$ ktorých je nekonečne veľa, tak táto podmnožina obsahuje iba tie vybrané kombinácie symbolov (slová) ktoré sú platné pre daný jazyk (dávajú zmysel, teda: spĺňajú pravidlá danej gramatiky).

Predstav si to, ako keby existovali všetky možné kombinácie písmen, bez ohľadu na to či by tie slová dávali zmysel alebo nie. To by predstavovala množina $V^{*}$, napríklad:

$$V^{*}=\{ϵ,a,b,c,\dots ,asdaf,asdag,\dots ,mama,\dots ,xyzhrbbdfu,\dots \}$$

Ak takáto množina obsahuje všetky kombinácie, ktorých je nekonečne veľa, tak potom podmnožina - jazyk $L$ - bude obsahovať iba tie slová, ktoré sú platné pre ten jazyk (spĺňajú pravidlá definované v gramatike). Napríklad: $L=\{mama\}$.

Zjednodušený zápis krokov odvodenia

Rekurzia sa využíva v gramatikách veľmi často, pretože nám dovoľuje generovať prakticky slová s nekonečnou dĺžkou. Ak by sme chceli vygenerovať veľmi dlhé číslo (napr.: milión), tak by sme iba neustále opakovali kroky odvodenia pokým by sme sa nedopracovali k výsledku.

Avšak, týchto krokov by bolo príliš veľa a pravdepodobne by sme ich nestihli napísať všetky dokým by sme neodpadli od únavy. Z tohto dôvodu sa zaviedol zjednodušený zápis krokov odvodenia. Teda, kroky odvodenia čísla "milión" by sme vyjadrili takto:

$$S{\Rightarrow }^{*}100000000$$

Zápis ${\Rightarrow }^{*}$ hovorí, že symbol $S$ sme nejakým spôsobom (ale takým, akým nám naša gramatika povoľuje) prepísali na jeden milión. Vyhli by sme sa tak zdĺhavému vypisovaniu jednotlivých krokov odvodenia, pretože by trvalo naozaj dlho kým by sme sa dostali k výsledku.

Gramatika vo formálnych jazykoch »