Capitolo C35:
famiglie astratte di linguaggi
Contenuti delle sezioni
a. operazioni di chiusura sulla collezione dei linguaggi p.3 b. coni razionali e famiglie astratte di linguaggi p.3 c. famiglie di linguaggi traslatabili e chiuse per crochet p.3 d. famiglie astratte di linguaggi di tipo full p.3
e. prefamiglie astratte di linguaggi p.3 f. famiglie astratte di linguaggi principali p.4 g. catene di fAFL p.4
h. applicazioni ai linguaggi lineari e simili p.4 i. teorema di rappresentazione p.4
j. gli a-trasduttori p.4
k. sostituzioni e linguaggi limitati p.5 l. conseguenze del lemma di sostituzione p.5
5 pagine
C35:0.01 Queste pagine sono dedicate alle famiglie astratte di linguaggi, cio`e alle collezioni di linguaggi definite assiomaticamente come insiemi di linguaggi che sono chiusi rispetto a un certo raggruppamento di operazioni sopra i linguaggi.
Per tali collezioni si usa il termine famiglie di linguaggi, mentre per noi il termine di famiglia richiede- rebbe la presenza di un insieme di indici [B19g09].
Intorno al 1966 Seymour Ginsburg e Sheila Greibach, ampliando un decennio di ricerche sulle propriet`a di chiusura rispetto a particolari operazioni, hanno definito come famiglie astratte di linguaggi, in acronimo AFL, le famiglie di linguaggi chiuse rispetto a uno specifico raggruppamento di operazioni:
unione, giustapposizione, chiusura-+, intersezione con linguaggi razionali, i cosiddetti skamorfismi-m noncancellanti e gli inversi di tali skamorfismi-m.
Successivamente sono state definite molte altre famiglie di linguaggi, a cominciare dalle “famiglie astratte di linguaggi di tipo full” in acronimo fAFL, pi`u ampie delle AFL in quanto chiuse anche rispetto a tutti gli skamorfismi-m.
Nel seguito useremo l’acronimo AFLgg per le famiglie di linguaggi introdotte da Ginsburg e Greibach, mentre useremo AFL per l’aggregato di tutte le famiglie di linguaggi associate a un qualche ragionevole
Lo studio delle AFL si propone di trovare, a partire dalle operazioni per le quali si richiedono le chiusure, propriet`a che siano soddisfatte da ampie collezioni di linguaggi e strumenti che si possano applicare a tali ampie collezioni.
Le pagine che seguono conducono questo studio a partire da considerazioni generali sopra le funzioni di chiusura agenti sopra la collezione di tutti i linguaggi sopra un generico alfabeto e avvalendosi sistematicamente della tecnica degli operatori unitivi sui monoidi liberi [C33].
Questo modo di fare porta a un sistema di dimostrazioni con buone caratteristiche di unitariet`a e quindi a un complesso di propriet`a dei linguaggi che alternativamente sono ottenibili con dimostrazioni da condurre sopra gli insiemi di dispositivi in genere in modo pi`u frammentario e meno organico.
C35:a. operazioni di chiusura sulla collezione dei linguaggi
C35: a.01 C35: a.02
C35:b. coni razionali e famiglie astratte di linguaggi
C35: b.01 C35: b.02
C35:c. famiglie di linguaggi traslatabili e chiuse per crochet
C35: c.01 C35: c.02
C35:d. famiglie di linguaggi traslatabili e chiuse per crochet
C35: d.01 C35: d.02
C35:e. prefamiglie astratte di linguaggi
C35: e.01 C35: e.02
C35:f. famiglie astratte di linguaggi principali
C35: f.01 C35: f.02
C35:g. catene di fAFL
C35: g.01 C35: g.02
C35:h. applicazioni ai linguaggi lineari e simili
C35: h.01 C35: h.02
C35:i. teorema di rappresentazione
C35: i.01 C35: i.02
C35:j. gli a-trasduttori
C35: j.01 C35: j.02
C35:k. sostituzioni e linguaggi limitati
C35: k.01 C35: k.02
C35:l. conseguenze del lemma di sostituzione
C35: l.01 C35: l.02
Testi dell’esposizione in http://www.mi.imati.cnr.it/alberto/ e in http://arm.mi.imati.cnr.it/Matexp/
