Formálny jazyk

**(Formálny) jazyk** je zovšeobecnenie pojmu jazyk z lingvistiky. 

Formálne jazyky, ich vlastnosti a modely na ich opis študuje teória formálnych jazykov v informatike. Na jazyky sa môžeme pozerať ako na problémy. Formalizácia tohto pojmu prináša možnosť s ním exaktne pracovať a tým aj dokazovať vlastnosti problémov, ktoré reprezentujú, či sa vôbec dajú riešiť a aké sú náročné na riešenie.

## Definícia
*Jazyk* nad abecedou \Sigma je ľubovoľná množina slov s konečnou dĺžkou nad touto konečnou abecedou.

## Príklady
Majme abecedu \Sigma = \{a, b, c\}. Jazyky nad touto abecedou sú napr.:
* L_1=\{aa, bb, cc\},
* L_2=\{a\},
* L_3=\{a, b, c\} = \Sigma,
* L_4=\emptyset, 
* L_5=\{a, aa, aaa, aaaa, \ldots\} = \{a^i~|~ i \ge 1\}, 
* L_6=\Sigma^*.

## Reprezentácia
Keďže formálne jazyky sú množiny, môžeme využiť všetky spôsoby reprezentácie množín, napr. vymenovanie prvkov pri konečných jazykoch alebo udanie logického predikátu nad množinou všetkých slov nad abecedou. V teórii formálnych jazykov boli vyvinuté dva veľmi silné modely, ktoré popisujú jazyky. Prvým je gramatika, ktorá svojimi pravidlami generuje slová z daného jazyka. Druhým modelom je automat. Na automat sa môžeme pozerať ako na čiernu skrinku, ktorá pre ľubovoľné slovo nad abecedou povie, či toto slovo patrí do daného jazyka alebo nie.

## Klasifikácia jazykov
V teórii formálnych jazykov delíme jazyky podľa sily modelov, ktoré ich popisujú, t. j. gramatík alebo automatov. V roku 1956 americký informatik a lingvista Noam Chomsky popísal hierarchiu jazykov, ktorú dnes poznáme ako Chomského hierarchia.

## Operácie nad jazykmi
Nech L_1, L_2 sú jazyky nad abecedou \Sigma:

Nad jazykmi sú definované, prirodzene, množinové operácie
* zjednotenie jazykov L_1\cup L_2 = \{w~|~ w \in L_1 \vee w \in L_2\},
* prienik jazykov L_1\cap L_2 = \{w~|~ w \in L_1 \wedge w \in L_2\},
* rozdiel jazykov L_1 \setminus L_2 = \{w~|~ w \in L_1 \wedge w \not\in L_2\},
* komplement jazyka L_1 = \Sigma^* \setminus L_1 (pozri nižšie definíciu Kleeneho uzáveru - jazyka \Sigma^*).

Ďalej sa definujú nasledovné základné operácie:
* zreťazenie jazykov L_1.L_2 = \{w_1.w_2~|~ w_1\in L_1 \wedge w_2\in L_2\}, kde w_1.w_2 je zreťazenie slov w_1 a w_2,
* mocnina jazyka je definovaná rekurzívne: L_1^0 = \{\varepsilon\}, L_1^i = L.L^{i-1}. Do i-tej mociny jazyka patria teda všetky slová, ktoré vznikli zreťazením i slov z jazyka L_1,
* Kleeneho hviezdička (Kleeneho uzáver, iterácia) jazyka L_1^* = \bigcup_{i=0}^{\infty} L_1^i. Do Kleeneho uzáveru jazyka L_1 patria teda všetky slová, ktoré dostaneme zreťazením ľubovoľného (aj nulového) počtu slov z jazyka L_1,
* Kleeneho plus (Kleeneho kladný uzáver, kladná iterácia) jazyka L_1^+ = \bigcup_{i=1}^{\infty}L_1^i
 . Obecne neplatí, že L_1^+ = L_1^*\setminus\{\varepsilon\} ; táto rovnosť platí len vtedy ak L_1  neobsahuje \varepsilon\ .
* homomorfizmus: Nech je dané zobrazenie h\colon \Sigma_1^*\to \Sigma_2^* medzi Kleeneho uzávermi abecied \Sigma_1 a \Sigma_2 také, že \forall w_1,w_2\in \Sigma_1^*: h(w_1.w_2)=h(w_1).h(w_2). Zobrazenia s touto vlastnosťou voláme homomorfizmus. *Obrazom jazyka* L\subseteq \Sigma_1^* v homomorfizme h nazývame jazyk h(L) = \{h(w)|w\in L\}.