Formálny jazyk

Z Wikipédie

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

[úprava] Definícia

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

[úprava] Príklady

Majme abecedu $Σ = {a, b, c}$ . Jazyky nad touto abecedou sú napr.:

$L 1 = {a a, b b, c c}$ ,
$L 2 = {a}$ ,
$L 3 = {a, b, c} = Σ$ ,
$L_4=\emptyset$ ,
$L_5=\{a, aa, aaa, aaaa, \ldots\} = \{a^i~|~ i \ge 1\}$ ,
$L 6 = Σ *$ .

[úprava] 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.

[úprava] 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.

[úprava] Operácie nad jazykmi

Nech $L 1, L 2$ sú jazyky nad abecedou $Σ$ :

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 $Σ *$ ).

Ď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 uvá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=L_1^*\setminus\{\varepsilon\}$ .,
homomorfizmus: Nech je dané zobrazenie $h\colon \Sigma_1^*\to \Sigma_2^*$ medzi Kleeneho uzávermi abecied $Σ 1$ a $Σ 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\}$ .

Formálne jazyky, automaty a gramatiky
Chomského hierarchia	Gramatiky	Jazyky	Minimálny automat
Typ-0	Frázová	Rekurzívne vyčísliteľný	Turingov stroj
		Rekurzívny	Vždy zastavujúci Turingov stroj
Typ-1	Kontextová	Kontextová	(Nedeterministický) lineárne ohraničený
Typ-2	Bezkontextová	Bezkontextový	(Nedeterministický) zásobníkový
Typ-3	Regulárna	Regulárny	Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.