Formellt språk

Ett formellt språk inom matematisk logik , datavetenskap och lingvistik är en uppsättning ändliga ord (strängar, kedjor) över ett ändligt alfabet . Begreppet språk används oftast inom automatteori , beräkningsbarhetsteori och algoritmteori . Den vetenskapliga teorin som behandlar detta objekt kallas teorin om formella språk .

I modellteori är ett språk byggt av uppsättningar av symboler, funktioner och relationer , tillsammans med deras aritet , såväl som en uppsättning variabler . Var och en av dessa uppsättningar kan vara oändliga. Från språket, tillsammans med universella logiska symboler , görs logiska uttalanden.

Definition

Ett formellt språk kan definieras på olika sätt, till exempel:

En enkel uppräkning av de ord som ingår i ett givet språk. Denna metod är främst tillämplig på definitionen av ändliga språk och språk med enkel struktur.
Ord som genereras av någon formell grammatik (se Chomsky-hierarki ).
Ord som genereras av det reguljära uttrycket .
Ord som känns igen av någon statsmaskin .
Ord som genereras av BNF-konstruktionen .

Om till exempel alfabetet anges som , och språket innehåller alla ord ovanför det, så tillhör ordet . Det tomma ordet (det vill säga en noll-längd sträng) är tillåtet och betecknas ofta som , eller . $\{a,b\}$ $L$ $ababba$ $L$ $e$ $\epsilon$ $\lambda$

Några andra exempel på formella språk:

set , där är ett icke- negativt tal , och betyder att det upprepas gånger; $\{a^{n}\}$ $n$ $a^{{n}}$ $a$ $n$
uppsättningen syntaktiskt korrekta program i ett givet programmeringsspråk .

Operationer

Vissa operationer kan användas för att generera nya språk från data. Antag att och är språk definierade över något vanligt alfabet. $L_{{1}}$ $L_{{2}}$

Sammankoppling (länkning) innehåller alla ord som uppfyller formen , var är ett ord från och är ett ord från . $L_{{1}}L_{{2}}$ $vw$ $v$ $L_{{1}}$ $w$ $L_{{2}}$
Korsningen innehåller alla ord som finns i både , och . $L_{1}\cap L_{2}$ $L_{1}$ $L_{{2}}$
Förbundet innehåller alla ord som finns i eller i . $L_{1}\kopp L_{2}$ $L_{{1}}$ $L_{{2}}$
Språkkomplementet innehåller alla ord i alfabetet som inte finns i . $L_{{1}}$ $L_{{1}}$
Den högra relationen innehåller alla ord för vilka det finns ett ord i sådan som fanns i . $L_{{1}}/L_{{2}}$ $v$ $w$ $L_{{2}}$ $vw$ $L_{{1}}$
Kleene-förslutningen innehåller alla ord som kan skrivas i formen där finns i och . Observera att detta inkluderar det tomma ordet också, eftersom det är tillåtet av villkoret. $L_{{1}}^{{*}}$ $w_{{1}}w_{{2}}...w_{{n}}$ $w_{{i}}$ $L_{{1}}$ $n\geq 0$ $\epsilon$ $n=0$
Inversionen innehåller inverterade ord från . $L_{{1}}^{{R}}$ $L_{{1}}$
Förvirringen och innehåller alla ord som kan skrivas i formen , där och är ord så att förhållandet är i , och är sådana ord som är i . $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}}$

Se även

Formell semantik

Litteratur

Gladkiy A. V. Formella grammatiker och språk. — M.: Nauka, 1973. — 368 sid.
Hopcroft J. , Motwani R. , Ullman J. An Introduction to Automatateory, Languages and Computing. - M .: Williams, 2002 (översatt av Addison Wesley). — 528 sid. — ISBN 5-8459-0261-4
Krevskiy I. G., Seliverstov M. N., Grigoryeva K. V. Formella språk, grammatik och grunderna för att konstruera översättare: Lärobok / Ed. A. M. Bershadsky. - Penza: Penz Publishing House. stat un-ta, 2002. - 124 sid.
Martynenko B.K. Språk och översättningar: Lärobok. - St. Petersburg: St. Petersburgs universitets förlag, 2003. - 235 sid.
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teori och implementering av programmeringsspråk - M.: MZ-Press, 2006, 2nd ed. — ISBN 5-94073-094-9
Pentus A. E., Pentus M. R. Matematisk teori om formella språk. - M .: Internet University of Information Technologies, Binom. Kunskapslaboratoriet, 2006. - 248 sid.
Fomichev V. S. Formella språk, grammatik och automater: Föreläsningskurs - Internetpublikation, 2006.
B.V. Biryukov. Formaliserat språk // New Philosophical Encyclopedia : i 4 volymer / föregående. vetenskaplig-ed. råd av V. S. Stepin . — 2:a uppl., rättad. och ytterligare - M . : Tanke , 2010. - 2816 sid.

Ordböcker och uppslagsverk

I bibliografiska kataloger
BNF : 11967270h GND : 4017848-1 J9U : 987007545721205171 LCCN : sh85050802 NDL : 00576869 NKC : ph208851

Formella språk och formella grammatiker
Allmänna begrepp	Chomsky hierarki Alfabet Ord
Typ 0	Obegränsad grammatik Turing maskin uppräknat språk Lösbart språk
Typ 1	Sammanhangskänslig grammatik Kontextkänsligt språk Linjärt begränsad automat
Typ 2	Kontextfri grammatik Tvetydig grammatik Kontextfritt språk Pushdown-automat ( deterministisk ) Tillväxt Lemma Ogdens Lemma Cooks teorem
Typ 3	Vanlig grammatik vanligt språk Vanligt uttryck Tillståndsmaskin ( deterministisk , icke- deterministisk ) DFA-minimering Bestämning av NFA Myhill-Nerodes sats
analysera	LL analysator LR-parser Rekursiv nedstigningsmetod Kok-Yngre-Kasami-algoritm