Abstrakt sprogfamilie

I teoretisk datalogi og især teori om formelle sprog henviser udtrykket abstrakte sprogfamilie til et koncept, der generaliserer de fælles kendetegn ved rationelt sprog , de algebraiske sprog , til rekursivt talbare sprog og mange andre familier med formelle sprog.

Definitioner

Et formelt sprog er et sæt ord over et endeligt alfabet , det vil sige en del af det frie monoid , hvor * betegner Kleenes stjerne . $L$ $PÅ$ $A ^ {*}$

En familie af sprog er et par dannet af et uendeligt alfabet betegnet og for enhver endelig del af et sæt formelle sprog på . $\ Sigma$ $PÅ$ $\ Sigma$ $PÅ$

En rationel kegle (kaldet full trio på engelsk) er en familie af lukkede sprog til drift af morfisme, omvendt morfisme og skæringspunkt med rationelle sprog.
En trofast rationel kegle (kaldet trio på engelsk) er en familie af lukkede sprog til operationer af ikke-sletende morfisme, omvendt morfisme og skæringspunkt med rationelle sprog.

En sprogfamilie er rationelt lukket, hvis den er lukket for fagforenings-, produkt- og Kleene-stjerneoperationer .
En abstrakt sprogfamilie ( fuld abstrakt sprogfamilie eller fuld AFL på engelsk) er en rationel kegle, der desuden er rationelt lukket.

Et abstrakt familietro sprog ( abstrakt familie af sprog eller AFL på engelsk) er en rationelt lukket trofast rationel kegle.

Vi møder også begrebet semi-AFL for en rationel kegle lukket af fagforening.

Eksempler på abstrakte familier af sprog og egenskaber

De rationelle sprog danner en abstrakt familie af sprog.

De algebraiske sprog danner familieabstrakte sprog.

De kontekstafhængige sprog danner et abstrakt familietro sprog, fordi de ikke er lukket af nogen morfisme.

De rekursivt talbare sprog udgør en abstrakt familie af trofaste sprog såvel som de rekursive sprog .

Hver rationel kegle indeholder familien af rationelle sprog.

De lineære sprog danner en rationel kegle lukket af union. Ligeledes danner kvasi-rationelle sprog en rationel kegle lukket af union. Lineære sprog er ikke rationelt lukkede, kvasi-rationelle sprog er.

Andre operationer udtrykkes ikke ved hjælp af rationelle transduktionsoperationer eller lukning for rationelle operationer. Disse er især blandingen , spejlbilledet, erstatningerne.

Oprindelse

Den første artikel, der beskæftiger sig med abstrakte sprogfamilier, blev præsenteret af Seymour Ginsburg og Sheila Greibach på det ottende symposium i serien Symposium om skift og automatteori i 1967.

Bemærkninger

(en) Ginsburg og Greibach (1967) .

Referencer

(en) Seymour Ginsburg og Sheila Greibach, "Abstrakte sprogfamilier " , i ottende årlige symposium om skift og automatteori, 18.-20. oktober 1967, Austin, Texas, USA , IEEE,1967, s. 128-139
(en) Seymour Ginsburg , algebraiske og automatiske teoretiske egenskaber ved formelle sprog , Nordholland,1975( ISBN 0-7204-2506-9 )
(en) John E. Hopcroft og Jeffrey D. Ullman, Introduktion til automatteori, sprog og beregning , Addison-Wesley,1979( ISBN 0-201-02988-X ) , "Kapitel 11: Lukningsegenskaber for sprogfamilier"
(en) Alexandru Mateescu og Arto Salomaa , "Kapitel 4: Aspekter af klassisk sprogteori" , i G. Rozenberg, A. Salomaa (red.), Handbook of Formal Languages , bind. 1: Word, Language, Grammatik , Springer Verlag,1997( ISBN 978-3540604204 ) , s. 175-252

Se også