Famiglia astratta di lingue

In informatica teorica , ed in particolare la teoria dei linguaggi formali , il termine famiglia lingue astratte si riferisce ad un concetto che generalizza le caratteristiche comuni di linguaggio razionale , le lingue algebriche , alle lingue ricorsivamente enumerabili e molte altre famiglie di linguaggi formali.

Definizioni

Un linguaggio formale è un insieme di parole su un alfabeto finito , cioè una parte del monoide libero , dove * denota la stella di Kleene . $L$ $A$ $A ^ {*}$

Una famiglia di lingue è una coppia formata da un alfabeto infinito denotato e, per ogni parte finita di , da un insieme di linguaggi formali in poi . $\ Sigma$ $A$ $\ Sigma$ $A$

Un cono razionale (chiamato full trio in inglese) è una famiglia di linguaggi chiusi per le operazioni di morfismo, morfismo inverso e intersezione con linguaggi razionali.
Un cono razionale fedele (chiamato trio in inglese) è una famiglia di linguaggi chiusi per operazioni di morfismo non cancellabile, morfismo inverso e intersezione con linguaggi razionali.

Una famiglia linguistica è chiusa razionalmente se è chiusa per operazioni di unione, prodotto e stella di Kleene .
Una famiglia astratta di lingue ( famiglia astratta completa di lingue o AFL completo in inglese) è un cono razionale che inoltre è razionalmente chiuso.

Una famiglia astratta fedele lingue ( famiglia astratta di lingue o AFL in inglese) è un cono razionale fedele razionalmente chiuso.

Incontriamo anche la nozione di semi-AFL per un cono razionale chiuso dall'unione.

Esempi di famiglie astratte di linguaggi e proprietà

I linguaggi razionali formano una famiglia astratta di linguaggi.

I linguaggi algebrici formano una famiglia linguaggi astratti.

I linguaggi contestuali formano una famiglia astratta linguaggi fedeli, perché non chiusi da alcun morfismo.

Le lingue ricorsivamente enumerabili formano una famiglia astratta di lingue fedeli così come le lingue ricorsive .

Ogni cono razionale contiene la famiglia dei linguaggi razionali.

I linguaggi lineari formano un cono razionale chiuso dall'unione. Allo stesso modo, i linguaggi quasi razionali formano un cono razionale chiuso dall'unione. I linguaggi lineari non sono chiusi razionalmente, i linguaggi quasi razionali lo sono.

Altre operazioni non sono espresse mediante operazioni di trasduzione razionale o chiusura per operazioni razionali. Questi sono in particolare lo shuffle , l'immagine speculare, le sostituzioni.

Origine

Il primo documento che trattava di famiglie astratte di linguaggi fu presentato da Seymour Ginsburg e Sheila Greibach all'ottavo simposio della serie Symposium on Switching and Automata Theory nel 1967.

Appunti

(en) Ginsburg e Greibach (1967) .

Riferimenti

(en) Seymour Ginsburg e Sheila Greibach, "Abstract Families of Languages" , in Eighth Annual Symposium on Switching and Automata Theory, 18-20 ottobre 1967, Austin, Texas, USA , IEEE,1967, p. 128-139
(en) Seymour Ginsburg , Algebraic and Automata Theoretic Properties of Formal Languages , North-Holland,1975( ISBN 0-7204-2506-9 )
(en) John E. Hopcroft e Jeffrey D.Ullman, Introduzione alla teoria, ai linguaggi e al calcolo degli automi , Addison-Wesley,1979( ISBN 0-201-02988-X ) , "Capitolo 11: Proprietà di chiusura delle famiglie di linguaggi"
(en) Alexandru Mateescu e Arto Salomaa , "Capitolo 4: Aspetti della teoria del linguaggio classico" , in G. Rozenberg, A. Salomaa (a cura di), Handbook of Formal Languages , vol. 1: parola, lingua, grammatica , springer verlag,1997( ISBN 978-3540604204 ) , p. 175-252

Vedi anche