Muodollinen kieli

Formaalikieli matemaattisessa logiikassa , tietojenkäsittelytieteessä ja kielitieteessä on joukko äärellisiä sanoja ( merkkijonoja , ketjuja) äärellisen aakkoston päällä . Kielen käsitettä käytetään yleisimmin automaatioteoriassa , laskettavuusteoriassa ja algoritmiteoriassa . Tätä objektia käsittelevää tieteellistä teoriaa kutsutaan muodollisten kielten teoriaksi .

Malliteoriassa kieli rakennetaan symbolien, funktioiden ja relaatioiden joukoista , niiden ariteettien sekä muuttujien joukosta . Jokainen näistä joukoista voi olla ääretön. Kielestä yhdessä universaalien loogisten symbolien kanssa tehdään loogisia lausuntoja.

Määritelmä

Muodollinen kieli voidaan määritellä useilla tavoilla, esimerkiksi:

Yksinkertainen luettelo tietyn kielen sanoista. Tämä menetelmä soveltuu pääasiassa äärellisten kielten ja yksinkertaisen rakenteen kielten määrittelyyn.
Formaalin kieliopin luomat sanat (katso Chomsky-hierarkia ).
Säännöllisen lausekkeen luomat sanat .
Jonkin tilakoneen tunnistamat sanat .
BNF-konstruktion luomat sanat .

Jos esimerkiksi aakkoset annetaan muodossa , ja kieli sisältää kaikki sen yläpuolella olevat sanat, sana kuuluu ryhmään . Tyhjä sana (eli nollapituinen merkkijono) on sallittu, ja se merkitään usein nimellä , tai . $\{a,b\}$ $L$ $Ababba$ $L$ $e$ $\epsilon$ $\lambda$

Muutamia muita esimerkkejä muodollisista kielistä:

set , jossa on ei- negatiivinen luku ja tarkoittaa, että se toistuu kertaa; $\{a^{n}\}$ $n$ $a^{{n}}$ $a$ $n$
joukko syntaktisesti oikeita ohjelmia tietyllä ohjelmointikielellä .

Toiminnot

Joitakin toimintoja voidaan käyttää uusien kielten luomiseen tiedoista. Oletetaan, että ja ovat kieliä, jotka on määritelty jonkin yleisen aakkoston perusteella. $L_{{1}}$ $L_{{2}}$

Yhdistelmä (linkki) sisältää kaikki sanat, jotka täyttävät muotoa , jossa on sana lähteestä ja sana lähteestä . $L_{{1}}L_{{2}}$ $vw$ $v$ $L_{{1}}$ $w$ $L_{{2}}$
Leikkaus sisältää kaikki sanat, jotka sisältyvät sekä , että . $L_{1}\cap L_{2}$ $L_{1}$ $L_{{2}}$
Liitto sisältää kaikki sanat, jotka sisältyvät . $L_{1}\kuppi L_{2}$ $L_{{1}}$ $L_{{2}}$
Kielen täydennys sisältää kaikki aakkosten sanat, jotka eivät sisälly . $L_{{1}}$ $L_{{1}}$
Oikea suhde sisältää kaikki sanat , joille on sellainen sana , joka oli kielessä . $L_{{1}}/L_{{2}}$ $v$ $w$ $L_{{2}}$ $vw$ $L_{{1}}$
Kleene-pääte sisältää kaikki sanat, jotka voidaan kirjoittaa muodossa, jossa on ja . Huomaa, että tämä sisältää myös tyhjän sanan , koska se sallii ehdon. $L_{{1}}^{{*}}$ $w_{{1}}w_{{2}}...w_{{n}}$ $w_{{i}}$ $L_{{1}}$ $n\geq 0$ $\epsilon$ $n = 0$
Käänteisversio sisältää käänteisiä sanoja kohteesta . $L_{{1}}^{{R}}$ $L_{{1}}$
Sekaannus ja sisältää kaikki sanat, jotka voidaan kirjoittaa muotoon , missä ja ovat sellaisia sanoja, joissa suhde on , ja ovat sellaisia sanoja, jotka ovat muodossa . $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}}$

Katso myös

Muodollinen semantiikka

Kirjallisuus

Gladkiy A. V. Muodolliset kieliopit ja kielet. - M.: Nauka, 1973. - 368 s.
Hopcroft J. , Motwani R. , Ullman J. Johdatus automaatioteoriaan, kieliin ja tietojenkäsittelyyn. - M .: Williams, 2002 (kääntäjä Addison Wesley). — 528 s. — ISBN 5-8459-0261-4
Krevskiy I. G., Seliverstov M. N., Grigorjeva K. V. Muodolliset kielet, kieliopit ja kääntäjien rakentamisen perusteet: Oppikirja / Toim. A. M. Bershadsky. - Penza: Penz Publishing House. osavaltio un-ta, 2002. - 124 s.
Martynenko B.K. Kielet ja käännökset: Oppikirja. - Pietari: Pietarin yliopiston kustantamo, 2003. - 235 s.
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Ohjelmointikielten teoria ja toteutus - M.: MZ-Press, 2006, 2. painos. — ISBN 5-94073-094-9
Pentus A. E., Pentus M. R. Formaalisten kielten matemaattinen teoria. - M .: Internet University of Information Technologies, Binom. Knowledge Laboratory, 2006. - 248 s.
Fomichev V. S. Muodolliset kielet, kieliopit ja automaatit: Luentokurssi - Internet-julkaisu, 2006.
B.V. Biryukov. Formalisoitu kieli // New Philosophical Encyclopedia : 4 osaa / esi. tieteellinen toim. V. S. Stepinin neuvo . — 2. painos, korjattu. ja ylimääräistä - M . : Ajatus , 2010. - 2816 s.

Sanakirjat ja tietosanakirjat

Bibliografisissa luetteloissa
BNF : 11967270h GND : 4017848-1 J9U : 987007545721205171 LCCN : sh85050802 NDL : 00576869 NKC : ph208851

Muodolliset kielet ja viralliset kieliopit
Yleiset käsitteet	Chomsky-hierarkia Aakkoset Sana
Tyyppi 0	Rajoittamaton kielioppi Turingin kone lueteltu kieli Ratkaiseva kieli
Tyyppi 1	Tilanneherkkä kielioppi Tilannekohtainen kieli Lineaarisesti rajattu automaatti
Tyyppi 2	Kontekstiton kielioppi Epäselvä kielioppi Kontekstiton kieli Työntöautomaatti ( deterministinen ) Kasvu Lemma Ogdenin Lemma Cookin lause
Tyyppi 3	Tavallinen kielioppi tavallinen kieli Tavallinen ilme Tilakone ( deterministinen , ei - deterministinen ) DFA-minimointi NFA:n määrittäminen Myhill-Neroden lause
jäsentäminen	LL analysaattori LR jäsentäjä Rekursiivinen laskeutumismenetelmä Kok-Younger-Kasami-algoritmi