(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.
Jazyk nad abecedou je ľubovoľná množina slov s konečnou dĺžkou nad touto konečnou abecedou.
Majme abecedu . Jazyky nad touto abecedou sú napr.:
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.
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.
Nech sú jazyky nad abecedou :
Nad jazykmi sú definované, prirodzene, množinové operácie
Ďalej sa definujú nasledovné základné operácie:
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. |
This article uses material from the Wikipedia Slovenčina article Formálny jazyk, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Obsah je dostupný pod licenciou CC BY-SA 4.0, pokiaľ nie je uvedené inak. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Slovenčina (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.