Construire tous les langages sans contexte à partir d'un ensemble de langages de base et de propriétés de fermeture?

Une façon de regarder les expressions régulières est une preuve constructive du fait suivant: il est possible de construire les langages réguliers en commençant par un petit ensemble de langages et en les combinant via un petit ensemble fixe de propriétés de fermeture. Plus précisément, si nous commençons par la langue vide, la langue contenant la chaîne vide et les langues de toutes les chaînes de caractères uniques, nous pouvons assembler toutes les langues régulières possibles en utilisant l'union, la concaténation et l'étoile de Kleene.

Existe-t-il un ensemble de langages de base et de propriétés de fermeture qui peuvent être utilisés pour générer tous et uniquement les langages sans contexte? (Pour clarifier: je ne demande pas si vous pouvez écrire des expressions régulières pour toutes les LFC, ce que je sais est impossible. Au lieu de cela, je me demande s'il existe un moyen de concevoir un cadre de type expression régulière pour les LFC basé sur le mêmes principes de base.)

C'est possible, mais peut-être pas exactement comme vous le demandez. Pour commencer, prenez le langage Dyck de toutes les chaînes de crochets correspondants sur deux paires de crochets, par exemple , ou plus abstraitement . { [ , ] , ( , ) } a 1 , b 1 , a 2 , b $D_2$$\{ [,], (,) \}$$a_1,b_1,a_2,b_2$

Ensuite, chaque langage sans contexte peut être obtenu à partir de utilisant des homomorphismes, des homomorphismes inverses et une intersection avec des langages réguliers. Les langages sans contexte sont appelés "le cône principal généré par ", dans les anciens livres notés . Voir une question connexe: " Quelles langues sont reconnues par les machines à guichet unique? "D 2 M ( D 2$D_2$$D_2$$\mathcal{M}(D_2)$

En fait, nous n'avons besoin que d'une seule de chaque opération (bien choisie). Chaque CFL peut s'écrire , où , sont des homomorphismes et est un langage régulier. Intuitivement, est un programme d'un PDA, mappe chaque instruction à la lettre lue, aux opérations push et pop de la pile. Enfin, code le bon comportement de la pile.g h R R g h D $g(h^{-1}(D_2) \cap R)$$g$$h$$R$$R$$g$$h$$D_2$

Ce résultat est lié au théorème de Chomsky – Schützenberger (ou comme on peut le voir dans wikipedia, l'un d'eux). La déclaration liée ici dans wikipedia (a) n'a pas besoin d'un homomorphisme inverse, tandis que (b) elle ne se limite pas à deux paires de crochets. Les théorèmes de ce type proviennent du domaine des «familles abstraites d'automates», où Ginsburg et Greibach sont des noms importants. Un résultat connexe de Nivat indique que les opérations de la forme pour fixes sont les transductions à états finis.g , h , $L \mapsto g(h^{-1}(L) \cap R)$$g,h,R$