Abstrakti kielten perhe

Vuonna tietojenkäsittelyteoria ja erityisesti teorian virallista kieltä , termi abstrakti kielten perhe tarkoittaa käsite, joka yleistää yhteisiä piirteitä rationaalisen kielen , The algebrallinen kieliä , jotta rekursiivisesti numeroituva kieliä ja monia muita perheitä muodollista kieltä.

Määritelmät

Muotokieleen on joukko sanoja yli rajallinen aakkoset , eli osa vapaan monoidi , jossa * merkitsee Kleene tähti . $L$ $AT$ $A ^ {*}$

Kieliperhe on pari, joka on muodostettu ääretön aakkoset merkitty ja mistä tahansa äärellinen osa on , joukosta muodollista kielillä . $Sigma$ $AT$ $Sigma$ $AT$

Rationaalinen kartio (kutsutaan täysi trio Englanti) on perhe suljetun kielet toiminnan morfismi, käänteinen morfismi ja leikkaa järkevä kieliä.
Uskollinen rationaalinen kartio (kutsutaan trio Englanti) on perhe suljetun kielistä toimintaa kuin pyyhkimisen morfismi, käänteinen morfismi ja leikkaa järkevä kieliä.

Kieliperhe on rationaalisesti suljettu, jos se on suljettu unioni-, tuote- ja Kleene-tähtioperaatioita varten .
Abstrakti kieliperhe ( täysi abstrakti kieliperhe tai täysi AFL Englanti) on järkevä kartio joka lisäksi on rationaalisesti suljettu.

Abstrakti perhe uskollinen kielillä ( abstrakti kieliperhe tai AFL Englanti) on järkevästi kiinni uskollinen järkevä kartio.

Tapaamme myös puoli-AFL : n käsityksen rationaalisesta kartiosta, jonka unioni sulkee.

Esimerkkejä abstrakteista kieli- ja ominaisuusperheistä

Kielet järkevä muoto abstraktin kieliperheeseen.

Algebrallinen kielet muodostavat perheen abstrakteja kieliä.

Tilannekohtaisia kielet muodostavat abstraktin perheen uskollinen kieliä, koska ne eivät ole suljettu millään morfismi.

Rekursiivisesti numeroituva kielet muodostavat abstraktin perheen uskollinen kielten sekä rekursiivinen kielillä .

Jokainen järkevä kartio sisältää järkevien kielten perheen.

Lineaarinen kielet muodostavat järkevän kartion suljettu liitto. Samoin lähes rationaaliset kielet muodostavat järkevän kartion, jonka unioni sulkee. Lineaariset kielet eivät ole rationaalisesti suljettuja, lähes rationaaliset kielet ovat.

Muita operaatioita ei ilmaista rationaalisilla transduktiotoiminnoilla tai sulkemalla rationaalisia toimintoja. Nämä ovat erityisesti sekoitus , peilikuva, korvaukset.

Alkuperä

Ensimmäisen abstraktien kielten perheitä käsittelevän asiakirjan esittivät Seymour Ginsburg ja Sheila Greibach kytkentä- ja automaatioteoriasarjan kahdeksannessa symposiumissa vuonna 1967.

Huomautuksia

(fi) Ginsburg ja Greibach (1967) .

Viitteet

(en) Seymour Ginsburg ja Sheila Greibach, "Abstraktit kielten perheet" , kahdeksannessa vuotuisessa vaihto- ja automaatioteorian symposiumissa, 18.-20. lokakuuta 1967, Austin, Texas, USA , IEEE,1967, s. 128-139
(en) Seymour Ginsburg , virallisten kielten algebralliset ja automateoreettiset ominaisuudet , Pohjois-Hollanti,1975( ISBN 0-7204-2506-9 )
(en) John E.Hopcroft ja Jeffrey D.Ullman, Johdatus automaatioteoriaan, kielet ja laskenta , Addison-Wesley,1979( ISBN 0-201-02988-X ) , "Luku 11: Kieliperheiden sulkemisominaisuudet"
(en) Alexandru Mateescu ja Arto Salomaa , "Luku 4: Klassisen kieliteorian näkökohdat" , julkaisussa G. Rozenberg, A. Salomaa (toimittajat), Handbook of Formal Languages , voi. 1: Sana, kieli, kielioppi , Springer Verlag,1997( ISBN 978-3540604204 ) , s. 175-252

Katso myös