Limbaj formal

Un limbaj formal în logica matematică , informatică și lingvistică este un set de cuvinte finite (șiruri, lanțuri) peste un alfabet finit . Conceptul de limbaj este cel mai frecvent utilizat în teoria automatelor , teoria computabilității și teoria algoritmilor . Teoria științifică care se ocupă de acest obiect se numește teoria limbajelor formale .

În teoria modelelor, un limbaj este construit din seturi de simboluri, funcții și relații , împreună cu aritatea lor , precum și un set de variabile . Fiecare dintre aceste seturi poate fi infinit. Din limbaj, împreună cu simbolurile logice universale , se fac afirmații logice.

Definiție

Un limbaj formal poate fi definit în mai multe moduri, de exemplu:

O simplă enumerare a cuvintelor incluse într-o limbă dată. Această metodă este aplicabilă în principal pentru definirea limbilor finite și a limbilor cu structură simplă.
Cuvinte generate de o gramatică formală (vezi ierarhia Chomsky ).
Cuvinte generate de expresia regulată .
Cuvinte recunoscute de o mașină de stat .
Cuvinte generate de construcția BNF .

De exemplu, dacă alfabetul este dat ca , iar limba include toate cuvintele de deasupra lui, atunci cuvântul aparține . Cuvântul gol (adică un șir de lungime zero) este permis și este adesea notat ca , sau . $\{a,b\}$ $L$ $ababba$ $L$ $e$ $\epsilon$ $\lambda$

Alte exemple de limbaje formale:

set , unde este un număr nenegativ și înseamnă că se repetă de ori; $\{a^{n}\}$ $n$ $a^{{n}}$ $A$ $n$
ansamblul de programe corecte din punct de vedere sintactic într-un limbaj de programare dat .

Operațiuni

Unele operațiuni pot fi folosite pentru a genera noi limbi din date. Să presupunem că și sunt limbi definite pe un alfabet comun. $L_{{1}}$ $L_{{2}}$

Concatenarea (legătura) conține toate cuvintele care satisfac forma , unde este un cuvânt de la și este un cuvânt de la . $L_{{1}}L_{{2}}$ $vw$ $v$ $L_{{1}}$ $w$ $L_{{2}}$
Intersecția conține toate cuvintele conținute în ambele , și . $L_{1}\cap L_{2}$ $L_{1}$ $L_{{2}}$
Unirea conține toate cuvintele conținute în sau în . $L_{1}\cup L_{2}$ $L_{{1}}$ $L_{{2}}$
Complementul de limbă conține toate cuvintele alfabetului care nu sunt conținute în . $L_{{1}}$ $L_{{1}}$
Relația corectă conține toate cuvintele pentru care există un cuvânt în așa care a fost în . $L_{{1}}/L_{{2}}$ $v$ $w$ $L_{{2}}$ $vw$ $L_{{1}}$
Închiderea Kleene conține toate cuvintele care pot fi scrise în forma unde este conținut în și . Rețineți că acest lucru include și cuvântul gol , deoarece este permis de condiție. $L_{{1}}^{{*}}$ $w_{{1}}w_{{2}}...w_{{n}}$ $w_{{i}}$ $L_{{1}}$ $n\geq 0$ $\epsilon$ $n=0$
Inversiunea conține cuvinte inversate din . $L_{{1}}^{{R}}$ $L_{{1}}$
Confuzia și conține toate cuvintele care pot fi scrise în forma , unde și sunt cuvinte astfel încât relația este în , și sunt astfel de cuvinte care sunt în . $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}}$

Vezi și

Semantică formală

Literatură

Gladkiy A. V. Gramatici și limbi formale. — M.: Nauka, 1973. — 368 p.
Hopcroft J. , Motwani R. , Ullman J. O introducere în teoria automatelor, limbaje și calcul. - M .: Williams, 2002 (traducere de Addison Wesley). — 528 p. — ISBN 5-8459-0261-4
Krevskiy I. G., Seliverstov M. N., Grigorieva K. V. Limbi formale, gramatici și elemente de bază ale construirii traducătorilor: Manual / Ed. A. M. Bershadsky. - Penza: Editura Penz. stat un-ta, 2002. - 124 p.
Martynenko B.K. Limbi și traduceri: manual. - Sankt Petersburg: Editura Universității din Sankt Petersburg, 2003. - 235 p.
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoria și implementarea limbajelor de programare - M.: MZ-Press, 2006, ed. a 2-a. — ISBN 5-94073-094-9
Pentus A. E., Pentus M. R. Teoria matematică a limbajelor formale. - M .: Internet University of Information Technologies, Binom. Laboratorul de cunoștințe, 2006. - 248 p.
Fomichev V. S. Limbi formale, gramatici și automate: Curs de prelegeri - publicație pe Internet, 2006.
B.V. Biryukov. Limbajul formalizat // Noua Enciclopedie Filosofică : în 4 volume / prev. științific-ed. sfatul lui V. S. Stepin . — Ed. a II-a, corectată. si suplimentare - M . : Gândirea , 2010. - 2816 p.

Dicționare și enciclopedii

În cataloagele bibliografice
BNF : 11967270h GND : 4017848-1 J9U : 987007545721205171 LCCN : sh85050802 NDL : 00576869 NKC : ph208851

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tip 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami