Formelt sprog

Et formelt sprog i matematisk logik , datalogi og lingvistik er et sæt af endelige ord (strenge, kæder) over et begrænset alfabet . Begrebet sprog bruges mest i automatteori , beregningsteori og algoritmeteori . Den videnskabelige teori, der beskæftiger sig med dette objekt, kaldes teorien om formelle sprog .

I modelteori er et sprog bygget af sæt af symboler, funktioner og relationer , sammen med deres aritet , samt et sæt af variabler . Hvert af disse sæt kan være uendelige. Fra sproget, sammen med universelle logiske symboler , laves logiske udsagn.

Definition

Et formelt sprog kan defineres på forskellige måder, for eksempel:

En simpel opregning af de ord, der indgår i et givet sprog. Denne metode er hovedsageligt anvendelig til definitionen af endelige sprog og sprog med enkel struktur.
Ord genereret af en eller anden formel grammatik (se Chomsky-hierarki ).
Ord genereret af det regulære udtryk .
Ord genkendt af en statsmaskine .
Ord genereret af BNF-konstruktionen .

For eksempel, hvis alfabetet er angivet som , og sproget omfatter alle ordene over det, så hører ordet til . Det tomme ord (det vil sige en streng på nul) er tilladt og betegnes ofte som , eller . $\{a,b\}$ $L$ $ababba$ $L$ $e$ $\epsilon$ $\lambda$

Nogle andre eksempler på formelle sprog:

set , hvor er et ikke- negativt tal , og betyder at det gentages gange; $\{a^{n}\}$ $n$ $a^{{n}}$ $-en$ $n$
sættet af syntaktisk korrekte programmer i et givet programmeringssprog .

Operationer

Nogle operationer kan bruges til at generere nye sprog ud fra data. Antag, at og er sprog defineret over et almindeligt alfabet. $L_{{1}}$ $L_{{2}}$

Sammenkædning (kobling) indeholder alle ord, der opfylder formen , hvor er et ord fra og er et ord fra . $L_{{1}}L_{{2}}$ $vw$ $v$ $L_{{1}}$ $w$ $L_{{2}}$
Skæringspunktet indeholder alle de ord, der er indeholdt i både , og . $L_{1}\cap L_{2}$ $L_{1}$ $L_{{2}}$
Fagforeningen indeholder alle de ord, der er indeholdt i eller i . $L_{1}\kop L_{2}$ $L_{{1}}$ $L_{{2}}$
Sprogkomplementet indeholder alle de ord i alfabetet, der ikke er indeholdt i . $L_{{1}}$ $L_{{1}}$
Den rigtige relation indeholder alle ord , for hvilke der er et ord i sådan, som var i . $L_{{1}}/L_{{2}}$ $v$ $w$ $L_{{2}}$ $vw$ $L_{{1}}$
Kleene-lukningen indeholder alle ord, der kan skrives i den form, hvor er indeholdt i og . Bemærk, at dette også inkluderer det tomme ord , da det er tilladt af betingelsen. $L_{{1}}^{{*}}$ $w_{{1}}w_{{2}}...w_{{n}}$ $w_{{i}}$ $L_{{1}}$ $n\geq 0$ $\epsilon$ $n=0$
Inversionen indeholder omvendte ord fra . $L_{{1}}^{{R}}$ $L_{{1}}$
Forvirringen og indeholder alle ord, der kan skrives i form , hvor og er ord sådan, at forholdet er i , og er sådanne ord, der er 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 også

Formel semantik

Litteratur

Gladkiy A. V. Formelle grammatikker og sprog. — M.: Nauka, 1973. — 368 s.
Hopcroft J. , Motwani R. , Ullman J. An Introduction to Automatateory, Languages and Computing. - M .: Williams, 2002 (oversat af Addison Wesley). — 528 s. — ISBN 5-8459-0261-4
Krevskiy I. G., Seliverstov M. N., Grigoryeva K. V. Formelle sprog, grammatik og grundlæggende for at konstruere oversættere: Lærebog / Ed. A. M. Bershadsky. - Penza: Penz Publishing House. stat un-ta, 2002. - 124 s.
Martynenko B.K. Sprog og oversættelser: Lærebog. - St. Petersburg: Forlaget ved St. Petersburg University, 2003. - 235 s.
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teori og implementering af programmeringssprog - M.: MZ-Press, 2006, 2. udg. — ISBN 5-94073-094-9
Pentus A. E., Pentus M. R. Matematisk teori om formelle sprog. - M .: Internet University of Information Technologies, Binom. Videnlaboratoriet, 2006. - 248 s.
Fomichev V. S. Formelle sprog, grammatik og automater: Forelæsningsforløb - Internetpublikation, 2006.
B.V. Biryukov. Formaliseret sprog // New Philosophical Encyclopedia : i 4 bind / prev. videnskabeligt udg. råd fra V. S. Stepin . — 2. udg., rettet. og yderligere - M . : Tanke , 2010. - 2816 s.

Ordbøger og encyklopædier

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

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme