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

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ť jednocifernú číslicu od nula po desať.

Našu gramatiku definujeme ako $G=(N,T,P,S)$ (v preklade: gramatika $G$ je štvorica $N$eterminálnych a $T$erminálnych symbolov s $P$ravidlami a začiatočným neterminálnym symbolom - teda substitučným symbolom, s ktorý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ísmená" z našej "NTPS" štvorice:

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

Čo zápis vyššie znamená?

• $N$ predstavuje množinu neterminálnych symbolov. Je to zoznam symbolov, ktoré môžeme nahradiť niečím iným.
• $T$ predstavuje množinu terminálnych symbolov. Sú to všetky symboly, z ktorých môže byť tvorené nejaké slovo

Ak ešte nechápeš čo sa tu deje, skúsime si to vysvetliť na pravidlách:

$$\begin{array}{r}P:\\ S& \to 0& S& \to 4& S& \to 8\\ S& \to 1& S& \to 5& S& \to 9\\ S& \to 2& S& \to 6\\ S& \to 3& S& \to 7\\ \end{array}$$

Definovali sme najdôležitejšiu časť každej gramatiky: pravidlá, pomocou ktorých sa symboly prepisujú na iné. Šípku ($\to$) čítame ako "symbol x sa prepíše na y".

Úplná definícia našej gramatiky (ktorá generuje práve jednu číslicu od nula po desať) vyzerá nasledovne:

$\begin{array}{rl}G& =(N,T,P,S)\\ N& =\{S\}\\ T& =⟨0,9⟩\\ \end{array}\begin{array}{r}\\ \end{array}$

$\begin{array}{rlrlrl}P:S& \to 0& S& \to 4& S& \to 8\\ S& \to 1& S& \to 5& S& \to 9\\ S& \to 2& S& \to 6\\ S& \to 3& S& \to 7\\ \end{array}$

Poďme skúsiť vygenerovať čislicu 4. Za začiatočný neterminálny symbol sme zvolili $S$ (je to posledný symbol zo štvorice v definícií našej gramatiky $G$, preto sme ho zvýraznili), takže týmto symbolom musíme aj začať. Čo bude nasledovať ďalej? Musíme tento symbol nahradiť niečím za šípkou v pravidlách (preto sa zápis "$S\to \dots$" číta ako "S sa prepíše na ..." - pretože sa skutočne prepíše na niečo iné... duh).

V zozname našich pravidiel vidíme pravidlo "$S\to 4$". A to je vlastne všetko a máme číslicu 4 ktorú sme chceli. Musíme to ale matematicky zapísať:

$$S\Rightarrow 4$$

Dôležité je použiť dvojitú šípku ($\Rightarrow$) namiesto jednoduchej ($\to$), pretože dvojitá šípka predstavuje takzvaný "krok odvodenia". Znamená to že sme prepísali neterminálny symbol S na 4. V jednom kroku môžeme použiť maximálne jedno pravidlo (teda, môžeme prepísať iba jeden neterminálny symbol na terminálny, nemôžme prepísať viacej symbolov naraz).

Slovo bolo vygenerované našou gramatikou správne, ak sa vo výsledku nenachádza žiadny neterminálny symbol (v našom prípade za neterminálny symbol podľa definície považujeme iba $S$). Vo výsledku sa za dvojitou šípkou nachádza iba 4, čo je symbol ktorý sme definovali v našej množine terminálnych symbolov ($T=⟨0,9⟩$). Znamená to, že naše slovo "4" patrí do našej gramatiky $G$, pretože tento výsledok obsahuje iba terminálne (konečné) symboly.

Čo dokážeme s gramatikou?

Príklad vyššie bol veľmi jednoduchý. Prepísali sme iba jeden neterminálny symbol na nejakú číslicu, a mali sme výsledné slovo z nášho jazyka číslic. Ale čo ak by sme mali za úlohu vytvoriť gramatiku ktorá bude generovať akékoľvek prirodzené číslo (celé číslo, ktoré je väčšie ako nula)?

Využijeme gramatiku z predchádzajúceho príkladu. Musíme ju avšak zmeniť tak, aby sme dokázali vygenerovať viac ako jeden symbol (a aby sme vynechali z pravidiel prepis na nulu).

Skúsme sa pozrieť na takéto pravidlá:

$$\begin{array}{r}P:\\ S& \to 1& S& \to 4& S& \to 7\\ S& \to 2& S& \to 5& S& \to 8\\ S& \to 3& S& \to 6& S& \to 9\\ \end{array}$$

Už sme z nich vynechali prepis na nulu. Avšak, ak musíme stále začať iba symbolom $S$, pravidlá nám povolia tento symbol prepísať iba na číslicu od 1 po 9 (vrátane). Ak by nás hneď nenapadlo riešenie, pravdepodobne by sme skúsili čísla nejako premiestniť na ľavú stranu (pred šípkou) aby sme nejako vygenerovali viac ako jednu číslicu a táto postupnosť by vytvorila číslo. Avšak, toto nie je povolené (podľa definície gramatiky musí ľavá strana vždy obsahovať neterminálny symbol, teda v tomto prípade naše $S$).

Riešenie v skutočnosti spočíva v rekurzií. Aby bolo riešenie čitateľné, musíme naše pravidlá trochu zmeniť:

$$\begin{array}{r}P:\\ S& \to cS& S& \to ϵ\\ c& \to 1& c& \to 4& c& \to 7\\ c& \to 2& c& \to 5& c& \to 8\\ c& \to 3& c& \to 6& c& \to 9\\ \end{array}$$

Pribudol nám nový neterminálny symbol $c$ (ako "číslo" - môžeme si zvoliť ľubovoľný symbol, dokonca by sme mohli pravidlá vyjadriť aj celým slovom, napríklad: $\text{číslo}\to \dots$, ale potom by bol zápis dlhý, preto to nebudeme komplikovať).

Zároveň sme pridali dve nové pravidlá pre neterminálny symbol $S$, kde využívame rekurziu:

• Symbol $S$ sa môže prepísať na číslo $c$, alebo sám na seba;
• Symbol $S$ sa môže prepísať na prázdne slovo (ktoré označujeme ako $ϵ$).

Poďme skúsiť vyjadriť číslo "123":

$$\begin{array}{lllll}\text{1.}& S& \Rightarrow & cS& \Rightarrow \\ \text{2.}& 1S& \Rightarrow & 1cS& \Rightarrow \\ \text{3.}& 12S& \Rightarrow & 12cS& \Rightarrow \\ \text{4.}& 123S& \Rightarrow & 123ϵ\\ \text{5.}& \Rightarrow 123\end{array}$$

To už vyzerá komplikovanejšie. Vysvetlíme si jednotlivé kroky:

1. V prvom kroku sme začali so symbolom $S$, ktorý sme prepísali na $cS$. Využili sme pritom prvé pravidlo ($S\to cS$). Tým sme zabezpečili to, že môžeme $c$ nahradiť číslicou, za ktorou bude nasledovať ďalšie $S$;
2. Za číslom ktoré sme nahradili nám zostalo opäť $S$, s ktorým sme aj začínali. Preto môžeme spraviť presne to isté, a $S$ prepísať opäť na $cS$;
3. $c$ sme nahradili číslicou 2. Posledný krát spravíme to isté, čo v predchádzajúcich krokoch odvodenia a opäť nahradíme $S$ za $cS$;
4. Posledný neterminálny symbol $c$ (ktorý zostal z tretieho kroku) sme prepísali na číslicu 3, čo je posledná číslica ktorú potrebujeme aby sme vytvorili číslo "123". Avšak, zostal nám tam stále symbol $S$, ktorý nasledoval za $c$. Pre to, aby bolo naše číslo platné, tak výsledok nesmie obsahovať neterminálny symbol $S$ - musíme tento symbol nejako odstrániť.
   • V tomto kroku využijeme druhé nové pravidlo, ktoré sme definovali ($S\to ϵ$) a $S$ prepíšeme na prázdne slovo $ϵ$. V tomto spočíva zmysel prázdneho slova, pretože predstavuje naozaj "nič" - už máme naše číslo 123, preto $S$ nahradíme "ničím", čím tento nadbytočný symbol v podstate odstránime;
5. Výsledné slovo je "123". Toto číslo skutočne patrí do jazyka prirodzených čísel väčších ako nula, takže naša gramatika je definovaná správne.

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 »