Familia abstractă de limbi

În informatică teoretică și, în special, teoria limbajelor formale , termenul familie de limbi abstracte se referă la un concept care generalizează caracteristicile comune ale limbajului rațional , limbajele algebrice , la limbaje recursiv enumerabile și multe alte familii de limbaje formale.

Definiții

Un limbaj formal este un set de cuvinte pe un alfabet finit , adică o parte a monoidului liber , unde * denotă steaua lui Kleene . $L$ $LA$ $A ^ {*}$

O familie de limbi este o pereche formată dintr - un alfabet infinit notat și, pentru orice parte finită a , dintr - un set de limbaje formale pe . $\ Sigma$ $LA$ $\ Sigma$ $LA$

Un con rațional (numit trio complet în engleză) este o familie de limbi închise pentru operațiile morfismului, morfismului invers și intersecției cu limbajele raționale.
Un con rațional fidel (numit trio în engleză) este o familie de limbi închise pentru operații de morfism care nu se șterge, morfism invers și intersecție cu limbaje raționale.

O familie de limbi este închisă în mod rațional dacă este închisă pentru operațiuni de unire, produs și stea Kleene .
O familie abstractă de limbi ( completă familie abstractă de limbi sau AFL completă în engleză) este un con rațional care, în plus, este închis rațional.

O limbă fidelă a familiei abstracte ( abstract family of languages sau AFL în engleză) este un con rațional fidel închis în mod rațional.

De asemenea, întâlnim noțiunea de semi-AFL pentru un con rațional închis prin uniune.

Exemple de familii abstracte de limbi și proprietăți

În limbile raționale formează o familie abstractă de limbi.

Cele Limbile algebrice formează o familie de limbi abstracte.

În limbile sensibile la context formează un rezumat de limbi credincioși de familie, pentru că acestea nu sunt închise de către orice morfism.

Limbile recursiv enumerabile formează o familie abstractă de limbi fidele, precum și limbile recursive .

Fiecare con rațional conține familia limbajelor raționale.

Cele Limbile liniare formează un con rațional închis de unire. La fel, limbajele cvasi-raționale formează un con rațional închis prin uniune. Limbile liniare nu sunt închise rațional, limbile cvasi-raționale sunt.

Alte operații nu sunt exprimate prin intermediul operațiilor de transducție rațională sau închiderea operațiunilor raționale. Acestea sunt, în special, amestecarea , imaginea în oglindă, substituțiile.

Origine

Prima lucrare care se ocupă de familii abstracte de limbi a fost prezentată de Seymour Ginsburg și Sheila Greibach la cel de-al optulea simpozion al seriei Simpozionul de comutare și teorie a automatelor din 1967.

Note

(ro) Ginsburg și Greibach (1967) .

Referințe

(ro) Seymour Ginsburg și Sheila Greibach, „Familii abstracte de limbi” , în cadrul celui de-al optulea simpozion anual privind comutarea și teoria automatelor, 18-20 octombrie 1967, Austin, Texas, SUA , IEEE,1967, p. 128-139
(ro) Seymour Ginsburg , Algebraic and Automata Theoretic Properties of Formal Languages , North-Holland,1975( ISBN 0-7204-2506-9 )
(ro) John E. Hopcroft și Jeffrey D. Ullman, Introducere în teoria automatelor, limbaje și calcul , Addison-Wesley,1979( ISBN 0-201-02988-X ) , "Capitolul 11: Proprietăți de închidere a familiilor de limbi"
(ro) Alexandru Mateescu și Arto Salomaa , „Capitolul 4: Aspecte ale teoriei limbajului clasic” , în G. Rozenberg, A. Salomaa (eds), Handbook of Formal Languages , vol. 1: Cuvânt, limbă, gramatică , Springer Verlag,1997( ISBN 978-3540604204 ) , p. 175-252

Vezi și tu