(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ú, čí sa vôbec dajú riešiť a aké sú náročné na riešenie.

Definícia

Jazyk nad abecedou $\backslash Sigma$ je ľubovoľná množina slov s konečnou dĺžkou nad touto konečnou abecedou.

Príklady

Majme abecedu $\backslash Sigma\; =\; \backslash \{a,\; b,\; c\backslash \}$. Jazyky nad touto abecedou sú napr.:

• $L\_1=\backslash \{aa,\; bb,\; cc\backslash \}$,
• $L\_2=\backslash \{a\backslash \}$,
• $L\_3=\backslash \{a,\; b,\; c\backslash \}\; =\; \backslash Sigma$,
• $L\_4=\backslash emptyset$,
• $L\_5=\backslash \{a,\; aa,\; aaa,\; aaaa,\; \backslash ldots\backslash \}\; =\; \backslash \{a^i~|~\; i\; \backslash ge\; 1\backslash \}$,
• $L\_6=\backslash 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 $\backslash Sigma$:

Nad jazykmi sú definované, prirodzene, množinové operácie

• zjednotenie jazykov $L\_1\backslash cup\; L\_2\; =\; \backslash \{w~|~\; w\; \backslash in\; L\_1\; \backslash vee\; w\; \backslash in\; L\_2\backslash \}$,
• prienik jazykov $L\_1\backslash cap\; L\_2\; =\; \backslash \{w~|~\; w\; \backslash in\; L\_1\; \backslash wedge\; w\; \backslash in\; L\_2\backslash \}$,
• rozdiel jazykov $L\_1\; -\; L\_2\; =\; \backslash \{w~|~\; w\; \backslash in\; L\_1\; \backslash wedge\; w\; \backslash not\backslash in\; L\_2\backslash \}$,
• komplement jazyka $L\_1\; =\; \backslash Sigma^*\; -\; L\_1$ (pozri nižšie definíciu Kleeneho uzáveru - jazyka $\backslash Sigma^*$).

Ďalej sa definujú nasledovné základné operácie:

• zreťazenie jazykov $L\_1.L\_2\; =\; \backslash \{w\_1.w\_2~|~\; w\_1\backslash in\; L\_1\; \backslash wedge\; w\_2\backslash in\; L\_2\backslash \}$, kde $w\_1.w\_2$ je zreťazenie slov $w\_1$ a $w\_2$,
• mocnina jazyka je definovaná rekurzívne: $L\_1^0\; =\; \backslash \{\backslash varepsilon\backslash \},\; 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 uváver, iterácia) jazyka $L\_1^*\; =\; \backslash bigcup\_\{i=0\}^\{\backslash 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^+\; =\; \backslash bigcup\_\{i=1\}^\{\backslash infty\}\; L\_1^i=L\_1^*-\backslash \{\backslash varepsilon\backslash \}$.,
• homomorfizmus: Nech je dané zobrazenie $h:\; \backslash Sigma\_1^*\backslash to\; \backslash Sigma\_2^*$ medzi Kleeneho uzávermi abecied $\backslash Sigma\_1$ a $\backslash Sigma\_2$ také, že $\backslash forall\; w\_1,w\_2\backslash in\; \backslash Sigma\_1^*:\; h(w\_1.w\_2)=h(w\_1).h(w\_2)$. Zobrazenia s touto vlastnosťou voláme homomorfizmus. Obrazom jazyka $L\backslash subseteq\; \backslash Sigma\_1^*$ v homomorfizme $h$ nazývame jazyk $h(L)\; =\; \backslash \{h(w)|w\backslash in\; L\backslash \}$.

Formálne jazyky a automaty

Формален език | Formální jazyk | Formale Sprache | Formal language | Lenguaje formal | Formaali kieli | Langage formel | Linguaggio formale (matematica) | 形式言語 | 형식 언어 | Formele taal | Język formalny | Linguagem formal | Limbaje formale | Формальный язык | Biçimsel dil kuramı | 形式语言