Formální jazyk

Formální jazyk v matematické logice , informatice a lingvistice je soubor konečných slov (řetězců, řetězců) přes konečnou abecedu . Pojem jazyka se nejčastěji používá v teorii automatů , teorii vyčíslitelnosti a teorii algoritmů . Vědecká teorie, která se tímto objektem zabývá, se nazývá teorie formálních jazyků .

V teorii modelů je jazyk vytvořen ze souborů symbolů, funkcí a vztahů spolu s jejich aritou a také ze sady proměnných . Každá z těchto množin může být nekonečná. Z jazyka se společně s univerzálními logickými symboly vytvářejí logické výroky.

Definice

Formální jazyk lze definovat různými způsoby, například:

Jednoduchý výčet slov obsažených v daném jazyce. Tato metoda je použitelná hlavně pro definici konečných jazyků a jazyků jednoduché struktury.
Slova generovaná nějakou formální gramatikou (viz Chomského hierarchie ).
Slova generovaná regulárním výrazem .
Slova rozpoznaná nějakým stavovým automatem .
Slova generovaná konstrukcí BNF .

Pokud je například abeceda uvedena jako , a jazyk zahrnuje všechna slova nad ní, pak slovo patří do . Prázdné slovo (tj. řetězec nulové délky) je povoleno a často se označuje jako , nebo . $\{a,b\}$ $L$ $ababba$ $L$ $E$ $\epsilon$ $\lambda$

Některé další příklady formálních jazyků:

set , kde je nezáporné číslo a znamená, že se opakuje krát; $\{a^{n}\}$ $n$ $a^{{n}}$ $A$ $n$
soubor syntakticky správných programů v daném programovacím jazyce .

Operace

Některé operace lze použít ke generování nových jazyků z dat. Předpokládejme, že a jsou jazyky definované v nějaké běžné abecedě. $L_{{1}}$ $L_{{2}}$

Zřetězení (vazba) obsahuje všechna slova, která splňují tvar , kde je slovo od a je slovo od . $L_{{1}}L_{{2}}$ $vw$ $proti$ $L_{{1}}$ $w$ $L_{{2}}$
Průsečík obsahuje všechna slova obsažená v obou , a . $L_{1}\cap L_{2}$ $L_{1}$ $L_{{2}}$
Sjednocení obsahuje všechna slova obsažená v nebo v . $L_{1}\pohár L_{2}$ $L_{{1}}$ $L_{{2}}$
Jazykový doplněk obsahuje všechna slova abecedy, která nejsou obsažena v . $L_{{1}}$ $L_{{1}}$
Správný vztah obsahuje všechna slova , pro která existuje slovo v takové, které bylo v . $L_{{1}}/L_{{2}}$ $proti$ $w$ $L_{{2}}$ $vw$ $L_{{1}}$
Uzávěr Kleene obsahuje všechna slova, která lze napsat ve formě , kde je obsaženo a . Všimněte si, že to zahrnuje i prázdné slovo , protože to podmínka umožňuje. $L_{{1}}^{{*}}$ $w_{{1}}w_{{2}}...w_{{n}}$ $w_{{i}}$ $L_{{1}}$ $n\geq 0$ $\epsilon$ $n=0$
Inverze obsahuje obrácená slova z . $L_{{1}}^{{R}}$ $L_{{1}}$
Zmatek a obsahuje všechna slova, která lze zapsat ve tvaru , kde a jsou slova taková, že vztah je v , a jsou taková slova, která jsou v . $L_{{1}}$ $L_{{2}}$ $v_{{1}}w_{{1}}v_{{2}}w_{{2}}...v_{{n}}w_{{n}}$ $n\geq 1$ $v_{{1}},...,v_{{n}}$ $v_{{1}}...v_{{n}}$ $L_{{1}}$ $w_{{1}},...,w_{{n}}$ $w_{{1}}...w_{{n}}$ $L_{{2}}$

Viz také

Formální sémantika

Literatura

Gladkiy A. V. Formální gramatiky a jazyky. — M.: Nauka, 1973. — 368 s.
Hopcroft J. , Motwani R. , Ullman J. Úvod do teorie automatů, jazyků a výpočetní techniky. - M.: Williams, 2002 (přeložil Addison Wesley). — 528 s. — ISBN 5-8459-0261-4
Krevskiy I. G., Seliverstov M. N., Grigoryeva K. V. Formální jazyky, gramatiky a základy konstrukce překladatelů: Učebnice / Ed. A. M. Bershadsky. - Penza: nakladatelství Penz. Stát un-ta, 2002. - 124 s.
Martynenko B.K. Jazyky a překlady: Učebnice. - Petrohrad: Nakladatelství Petrohradské univerzity, 2003. - 235 s.
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teorie a implementace programovacích jazyků - M.: MZ-Press, 2006, 2. vyd. — ISBN 5-94073-094-9
Pentus A. E., Pentus M. R. Matematická teorie formálních jazyků. - M .: Internetová univerzita informačních technologií, Binom. Vědomostní laboratoř, 2006. - 248 s.
Fomichev V. S. Formální jazyky, gramatiky a automaty: Kurz přednášek - internetová publikace, 2006.
B. V. Birjukov. Formalizovaný jazyk // Nová filozofická encyklopedie : ve 4 svazcích / předchozí. vědecky vyd. rada V. S. Stepina . — 2. vyd., opraveno. a doplňkové - M . : Myšlenka , 2010. - 2816 s.

Slovníky a encyklopedie

V bibliografických katalozích
BNF : 11967270h GND : 4017848-1 J9U : 987007545721205171 LCCN : sh85050802 NDL : 00576869 NKC : ph208851

Formální jazyky a formální gramatiky
Obecné pojmy	Chomského hierarchie Abeceda Slovo
Typ 0	Neomezená gramatika Turingův stroj výčtový jazyk Řešitelný jazyk
Typ 1	Kontextově citlivá gramatika Kontextový jazyk Lineárně ohraničený automat
Typ 2	Bezkontextová gramatika Nejednoznačná gramatika Bezkontextový jazyk Zásobníkový automat ( deterministický ) Růstové lemma Ogdenovo lemma Cookova věta
Typ 3	Pravidelná gramatika regulární jazyk Regulární výraz Stavový stroj ( deterministický , nedeterministický ) Minimalizace DFA Stanovení NFA Myhillova-Nerodova věta
rozebrat	LL analyzátor LR analyzátor Metoda rekurzivního sestupu Kok-Younger-Kasami algoritmus