Famille abstraite de langues - Abstract family of languages

Dans l'informatique , en particulier dans le domaine du langage formel théorie, une famille abstraite des langues est une notion mathématique abstraite caractéristiques généralisant communes aux langues régulières , les langues sans contexte et les langues récursivement énumérables , et d' autres familles de langues officielles étudiées dans la littérature scientifique.

Définitions formelles

Un langage formel est un ensemble L pour lequel il existe un ensemble fini de symboles abstraits Σ tels que , où * est l' opération en étoile de Kleene . ${\ displaystyle L \ subseteq \ Sigma ^ {*}}$

Une famille de langues est une paire ordonnée , où ${\ displaystyle (\ Sigma, \ Lambda)}$

1. Σ est un ensemble infini de symboles;
2. Λ est un ensemble de langages formels;
3. Pour chaque L dans Λ, il existe un sous-ensemble fini tel que ; et ${\ displaystyle \ Sigma _ {1} \ subset \ Sigma}$${\ displaystyle L \ subseteq \ Sigma _ {1} ^ {*}}$
4. L ≠ Ø pour certains L dans Λ .

Un trio est une famille de langues fermées sous homomorphisme e sans , inverse homomorphisme , et l' intersection avec la langue régulière.

Un trio complet, également appelé cône , est un trio fermé sous homomorphisme arbitraire.

Un semi-AFL (complet) est un trio (complet) fermé sous l' union .

Un AFL (complet) est un semi-AFL (complet) fermé sous concaténation et le Kleene plus .

Quelques familles de langues

Voici quelques résultats simples de l'étude de familles abstraites de langues.

Dans la hiérarchie Chomsky , les langues régulières, les langues sans contexte et les langues récursivement énumérables sont toutes des AFL complètes. Cependant, les langages sensibles au contexte et les langages récursifs sont des AFL, mais pas des AFL complètes car ils ne sont pas fermés sous des homomorphismes arbitraires.

La famille des langues régulières est contenue dans n'importe quel cône (trio complet). D'autres catégories de familles abstraites sont identifiables par fermeture sous d'autres opérations telles que le mélange, l'inversion ou la substitution.

Origines

Seymour Ginsburg de l' Université de Californie du Sud et Sheila Greibach de l'Université de Harvard ont présenté le premier article sur la théorie AFL au huitième symposium annuel de l'IEEE sur la théorie de la commutation et des automates en 1967.

Remarques

Les références

• Ginsburg, Seymour; Greibach, Sheila (1967). "Familles abstraites de langues". Compte rendu de conférence de 1967 Huitième symposium annuel sur la théorie de la commutation et des automates, 18–20 octobre 1967, Austin, Texas, États-Unis . IEEE. 128-139.
• Seymour Ginsburg, Propriétés théoriques algébriques et automates des langages formels , Hollande du Nord, 1975, ISBN   0-7204-2506-9 .
• John E. Hopcroft et Jeffrey D. Ullman, Introduction à la théorie des automates, aux langages et au calcul , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN   0-201-02988-X . Chapitre 11: Propriétés de fermeture des familles de langues.
• Mateescu, Alexandru; Salomaa, Arto (1997). "Chapitre 4: Aspects de la théorie classique du langage". À Rozenberg, Grzegorz; Salomaa, Arto (éd.). Manuel des langues formelles. Volume I: Mot, langue, grammaire . Springer-Verlag. 175–252. ISBN   3-540-61486-9 .