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

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é 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\}$.

Gramatika

V predošlých pojmoch sa vyskytla aj gramatika. Gramatika $G$ generuje iba slová ktoré patria do jazyka $L$ a žiadne iné.

Gramatika je definovaná ako štvorica ($G=(N,T,P,S)$), kde:

• ˆ$N$ je konečná neprázdna množina neterminálnych symbolov,
• $T$ je konečná neprázdna množina terminálnych symbolov, pričom $N\cap T=\mathrm{\varnothing }$ (to znamená, že tieto dve množiny nemajú spoločný žiadny symbol - symbol nemôže byť zároveň aj terminálny aj neterminálny),
• ˆ$P$ je konečná neprázdna množina pravidiel v tvare $\alpha \to \beta$, kde:
  • ľavá strana pravidiel $\alpha$ je ľubovoľný reťazec obsahujúci aspoň jeden neterminálny symbol $\alpha \in (N\cup T{)}^{*}N(N\cup T{)}^{*}$, a
  • pravá strana pravidiel $\beta$ je ľubovoľný reťazec $\beta \in (N\cup T{)}^{*}$,
• ˆ$S\in N$ je začiatočný neterminálny symbol.

Definícia môže vyzerať naozaj strašne pre niekoho kto nevie čítať matematické zápisy. V takom prípade stačí, ak si zapamätá:

1. Pomocou gramatiky generujeme nejaké slovo ktoré jednoznačne patrí iba do jedného konkrétneho jazyka (napríklad: môžeme definovať gramatiku pre generovanie čísiel od 0 po 9 a naše pravidlá zabezpečia že výsledok bude vždy iba nejaké číslo, nie napríklad písmeno);
2. Gramatika funguje tak, že najskôr definujeme pravidlá pre postupné nahrádzanie dočasných (neterminálnych) symbolov konkrétnymi konečnými (terminálnymi) symbolmi;
3. Vždy definujeme neterminálny symbol, z ktorého vychádzame. Ak nezostane nič, čo by sme mohli nahradiť, máme výsledok;

Príklad

Poďme si gramatiku ukázať na príklade. Zadanie hovorí, že máme definovať gramatiku $G$, ktorá bude generovať iba jednociferné číslice od nula po desať.

Teda, ju definujeme ako $G=(N,T,P,S)$ (to znamená: gramatika $G$ je štvorica $N$eterminálnych a $T$erminálnych symbolov s $P$ravidlami a začiatočným neterminálnym symbolom, teda tým s čím začíname, a tento symbol má označenie $S$ - môžeme zvoliť akékoľvek označenie, ale najčastejšie sa používa S).

Teraz definujeme jednotlivé "písmenká" z našej "NTPS" štvorice:

$\begin{array}{rl}N& =\{S\}\\ T& =\{0,1,2,3,4,5,6,7,8,9\}\end{array}$

Pravidlá definujeme ako:

Gramatika vo formálnych jazykoch »