Ú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$.

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é kombinácie symbolov z abecedy $V$ ktorých je nekonečne veľa, tak táto podmnožina obsahuje iba tie vybrané symboly 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.:

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

Tak potom podmnožina - jazyk $L$ - bude obsahovať iba tie kombinácie ktoré obsahujú platné slová pre ten jazyk. Napríklad: mama.

Gramatika vo formálnych jazykoch »