Formálny jazyk

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

(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[upraviť | upraviť zdroj]

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

Príklady[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

Nech L_1, L_2 sú jazyky nad abecedou \Sigma:

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

Ď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=L_1^*\setminus\{\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\}.
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.