# 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 WIKINIUM\_MATH\_PH\_0 je ľubovoľná množina slov s konečnou dĺžkou nad touto konečnou abecedou.

## Príklady

Majme abecedu WIKINIUM\_MATH\_PH\_2 . Jazyky nad touto abecedou sú napr.:

* WIKINIUM\_MATH\_PH\_4 ,
* WIKINIUM\_MATH\_PH\_6 ,
* WIKINIUM\_MATH\_PH\_8 ,
* WIKINIUM\_MATH\_PH\_10 ,
* WIKINIUM\_MATH\_PH\_12 ,
* WIKINIUM\_MATH\_PH\_14 .

## 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 WIKINIUM\_MATH\_PH\_16 sú jazyky nad abecedou WIKINIUM\_MATH\_PH\_18 :

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

* zjednotenie jazykov WIKINIUM\_MATH\_PH\_20 ,
* prienik jazykov WIKINIUM\_MATH\_PH\_22 ,
* rozdiel jazykov WIKINIUM\_MATH\_PH\_24 ,
* komplement jazyka WIKINIUM\_MATH\_PH\_26 (pozri nižšie definíciu Kleeneho uzáveru - jazyka WIKINIUM\_MATH\_PH\_28 ).

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

* zreťazenie jazykov WIKINIUM\_MATH\_PH\_30 , kde WIKINIUM\_MATH\_PH\_32 je zreťazenie slov WIKINIUM\_MATH\_PH\_34 a WIKINIUM\_MATH\_PH\_36 ,
* mocnina jazyka je definovaná rekurzívne: WIKINIUM\_MATH\_PH\_38 . Do WIKINIUM\_MATH\_PH\_40 -tej mociny jazyka patria teda všetky slová, ktoré vznikli zreťazením WIKINIUM\_MATH\_PH\_42 slov z jazyka WIKINIUM\_MATH\_PH\_44 ,
* Kleeneho hviezdička (Kleeneho uzáver, iterácia) jazyka WIKINIUM\_MATH\_PH\_46 . Do Kleeneho uzáveru jazyka WIKINIUM\_MATH\_PH\_48 patria teda všetky slová, ktoré dostaneme zreťazením ľubovoľného (aj nulového) počtu slov z jazyka WIKINIUM\_MATH\_PH\_50 ,
* Kleeneho plus (Kleeneho kladný uzáver, kladná iterácia) jazyka WIKINIUM\_MATH\_PH\_52 . Obecne neplatí, že WIKINIUM\_MATH\_PH\_54 ; táto rovnosť platí len vtedy ak WIKINIUM\_MATH\_PH\_56 neobsahuje WIKINIUM\_MATH\_PH\_58 .
* homomorfizmus: Nech je dané zobrazenie WIKINIUM\_MATH\_PH\_60 medzi Kleeneho uzávermi abecied WIKINIUM\_MATH\_PH\_62 a WIKINIUM\_MATH\_PH\_64 také, že WIKINIUM\_MATH\_PH\_66 . Zobrazenia s touto vlastnosťou voláme homomorfizmus. *Obrazom jazyka* WIKINIUM\_MATH\_PH\_68 v homomorfizme WIKINIUM\_MATH\_PH\_70 nazývame jazyk WIKINIUM\_MATH\_PH\_72 .

| Formálne jazyky, automaty a gramatiky |
| --- |
| **Chomského hierarchia** | **Gramatika** | **Jazyk** | **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. |