Hivatalos nyelv

A formális nyelv a matematikai logikában , számítástechnikában és nyelvészetben véges szavak (karakterláncok, láncok) halmaza egy véges ábécé felett . A nyelv fogalmát leggyakrabban az automataelméletben , a kiszámíthatóságelméletben és az algoritmuselméletben használják . Az ezzel a tárggyal foglalkozó tudományos elméletet formális nyelvek elméletének nevezik .

A modellelméletben egy nyelv szimbólumok, függvények és relációk halmazaiból épül fel , ezek aritásával együtt , valamint változók halmazából . Ezen halmazok mindegyike végtelen lehet. A nyelvből az univerzális logikai szimbólumokkal együtt logikai állítások születnek.

Definíció

Egy formális nyelv többféleképpen definiálható, például:

Egy adott nyelvben szereplő szavak egyszerű felsorolása. Ez a módszer elsősorban véges nyelvek és egyszerű szerkezetű nyelvek meghatározására alkalmazható.
Valamilyen formális nyelvtan által generált szavak (lásd Chomsky-hierarchia ).
A reguláris kifejezés által generált szavak .
Valamilyen állapotgép által felismert szavak .
A BNF konstrukció által generált szavak .

Például, ha az ábécé így van megadva , és a nyelv tartalmazza az összes felette lévő szót, akkor a szó a -hoz tartozik . Az üres szó (vagyis egy nulla hosszúságú karakterlánc) megengedett, és gyakran , vagy . $\{a,b\}$ $L$ $abba$ $L$ $e$ $\epsilon$ $\lambda$

Néhány példa a formális nyelvekre:

set , ahol egy nem negatív szám , és azt jelenti, hogy többször ismétlődik ; $\{a^{n}\}$ $n$ $a^{{n}}$ $a$ $n$
a szintaktikailag helyes programok halmaza egy adott programnyelvben .

Műveletek

Egyes műveletek felhasználhatók új nyelvek generálására az adatokból. Tegyük fel, hogy a és nyelvek valamilyen közös ábécé alapján vannak meghatározva. $L_{{1}}$ $L_{{2}}$

Az összefűzés (linkage) tartalmazza az összes olyan szót, amely megfelel a formának , ahol egy szó -ból és egy szó -ból . $L_{{1}}L_{{2}}$ $vw$ $v$ $L_{{1}}$ $w$ $L_{{2}}$
A metszéspont tartalmazza az összes szót, amelyet mind a , mind a . $L_{1}\sapka L_{2}$ $L_{1}$ $L_{{2}}$
Az unió tartalmazza az összes szót, amely a vagy -ban található . $L_{1}\pohár L_{2}$ $L_{{1}}$ $L_{{2}}$
A nyelvi kiegészítés tartalmazza az ábécé összes olyan szavát, amelyet nem tartalmaz . $L_{{1}}$ $L_{{1}}$
A helyes reláció tartalmazza az összes olyan szót , amelyre olyan szó van , amely benne volt . $L_{{1}}/L_{{2}}$ $v$ $w$ $L_{{2}}$ $vw$ $L_{{1}}$
A Kleene-zárás tartalmazza az összes olyan szót, amely olyan formában írható, ahol a és az szerepel . Vegye figyelembe, hogy ez magában foglalja az üres szót is, mivel ezt a feltétel lehetővé teszi. $L_{{1}}^{{*}}$ $w_{{1}}w_{{2}}...w_{{n}}$ $w_{{i}}$ $L_{{1}}$ $n\geq 0$ $\epsilon$ $n=0$
Az inverzió fordított szavakat tartalmaz . $L_{{1}}^{{R}}$ $L_{{1}}$
A és az összetévesztés tartalmazza az összes olyan szót, amely a formában írható , ahol és olyan szavak, amelyekben a kapcsolat van , és olyan szavak, amelyek -ben vannak . $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}}$

Lásd még

Formális szemantika

Irodalom

Gladkiy A. V. Formális nyelvtanok és nyelvek. — M.: Nauka, 1973. — 368 p.
Hopcroft J. , Motwani R. , Ullman J. Bevezetés az automataelméletbe, a nyelvekbe és a számítástechnikába. - M .: Williams, 2002 (fordította Addison Wesley). — 528 p. — ISBN 5-8459-0261-4
Krevskiy I. G., Seliverstov M. N., Grigoryeva K. V. Formális nyelvek, nyelvtan és a fordítók felépítésének alapjai: Tankönyv / Szerk. A. M. Bershadsky. - Penza: Penz Publishing House. állapot un-ta, 2002. - 124 p.
Martynenko B.K. Nyelvek és fordítások: Tankönyv. - Szentpétervár: Szentpétervári Egyetem Kiadója, 2003. - 235 p.
Szerebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Programozási nyelvek elmélete és megvalósítása - M.: MZ-Press, 2006, 2. kiadás. — ISBN 5-94073-094-9
Pentus A. E., Pentus M. R. Formális nyelvek matematikai elmélete. - M .: Internetes Információs Technológiai Egyetem, Binom. Tudáslaboratórium, 2006. - 248 p.
Fomichev V. S. Formális nyelvek, nyelvtanok és automaták: Előadások kurzusa - Internetes kiadvány, 2006.
B. V. Birjukov. Formalizált nyelv // Új Filozófiai Enciklopédia : 4 kötetben / előz. tudományos-szerk. V. S. Stepin tanácsa . — 2. kiadás, javítva. és további - M . : Gondolat , 2010. - 2816 p.

Szótárak és enciklopédiák

Bibliográfiai katalógusokban
BNF : 11967270h GND : 4017848-1 J9U : 987007545721205171 LCCN : sh85050802 NDL : 00576869 NKC : ph208851

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus