Abstrakt familie av språk

I teoretisk informatikk , og særlig teori om formelle språk , refererer begrepet abstrakte språkfamilie til et konsept som generaliserer de vanlige egenskapene til rasjonelt språk , de algebraiske språkene , til rekursivt tallrike språk og mange andre familier med formelle språk.

Definisjoner

Et formelt språk er et sett med ord over et endelig alfabet , det vil si en del av det frie monoiden , der * betegner Kleenes stjerne . $L$ $PÅ$ $A ^ {*}$

En språkfamilie er et par dannet av et uendelig alfabet betegnet og, for enhver endelig del av , fra et sett med formelle språk . $\ Sigma$ $PÅ$ $\ Sigma$ $PÅ$

En rasjonell kjegle (kalt full trio på engelsk) er en familie av lukkede språk for drift av morfisme, omvendt morfisme og skjæringspunkt med rasjonelle språk.
En trofast rasjonell kjegle (kalt trio på engelsk) er en familie av lukkede språk for operasjoner med ikke-slettende morfisme, omvendt morfisme og skjæringspunkt med rasjonelle språk.

En språkfamilie er rasjonelt stengt hvis den er stengt for fagforenings-, produkt- og Kleene-stjerneoperasjoner .
En abstrakt familie av språk ( full abstrakt språkfamilie eller full AFL på engelsk) er en rasjonell kjegle som i tillegg er rasjonelt lukket.

En abstrakt familietro språk ( abstrakt familie av språk eller AFL på engelsk) er en rasjonelt lukket trofast rasjonell kjegle.

Vi møter også begrepet semi-AFL for en rasjonell kjegle stengt av fagforening.

Eksempler på abstrakte familier av språk og egenskaper

De språkene rasjonell danner et abstrakt språkfamilien.

De algebraiske språkene danner et familieabstrakt språk.

De kontekstsensitive språkene danner et abstrakt familietro språk, fordi de ikke er lukket av morfisme.

De rekursivt tallrike språkene danner en abstrakt familie av trofaste språk så vel som de rekursive språkene .

Hver rasjonelle kjegle inneholder familien av rasjonelle språk.

De lineære språkene danner en rasjonell kjegle lukket av union. På samme måte danner kvasi-rasjonelle språk en rasjonell kjegle stengt av union. Lineære språk er ikke rasjonelt lukket, det er kvasi-rasjonelle språk.

Andre operasjoner uttrykkes ikke ved hjelp av rasjonelle transduksjonsoperasjoner eller stenging for rasjonelle operasjoner. Dette er spesielt stokkingen , speilbildet, erstatningene.

Opprinnelse

Den første artikkelen om abstrakte familier av språk ble presentert av Seymour Ginsburg og Sheila Greibach på det åttende symposiet i serien Symposium on Switching and Automata Theory i 1967.

Merknader

(en) Ginsburg og Greibach (1967) .

Referanser

(no) Seymour Ginsburg og Sheila Greibach, “Abstrakte familier av språk” , i det åttende årlige symposiet om bytte og automatteori, 18.-20. oktober 1967, Austin, Texas, USA , IEEE,1967, s. 128-139
(no) Seymour Ginsburg , algebraiske og automatteoretiske egenskaper for formelle språk , Nord-Holland,1975( ISBN 0-7204-2506-9 )
(en) John E. Hopcroft og Jeffrey D. Ullman, Introduksjon til automatteori, språk og beregning , Addison-Wesley,1979( ISBN 0-201-02988-X ) , "Kapittel 11: Lukkingsegenskaper for språkfamilier"
(en) Alexandru Mateescu og Arto Salomaa , “Chapter 4: Aspects of Classical Language Theory” , i G. Rozenberg, A. Salomaa (redaktører), Handbook of Formal Languages , vol. 1: Ord, språk, grammatikk , Springer Verlag,1997( ISBN 978-3540604204 ) , s. 175-252

Se også