Quelle est la puissance des CFG qui permettent un nombre infini de règles?

Je me demandais récemment ce qui se passerait si nous permettions aux grammaires sans contexte d'avoir un nombre infini de règles. De toute évidence, si nous permettions arbitrairement de tels ensembles infinis de règles, chaque langue sur un alphabet pourrait être décrite par un CFG avec . Mais que se passe-t-il si nous limitons à de tels ensembles de règles qui peuvent être créés par des grammaires sans contexte?Σ G = ( { S } , Σ , R , S ) R = { S → w ∣ w ∈ L } $L$$\Sigma$$G = (\{S\},\Sigma,R,S)$$R = \{S \rightarrow w \mid w \in L \}$$R$

À cet effet, étant donné un ensemble de terminaux et de terminaux , considérons les règles non pas comme des éléments de , mais comme des chaînes de l'alphabet R _ {(N, \ Sigma) } = N \ cup \ Sigma \ cup \ {\ rightarrow \} . Maintenant, ma question est, si nous définissons une règle infinie CFG pour être un tuple G = (N, \ Sigma, R, S) oùΣ N × ( N ∪ Σ ) ∗ R ( N , Σ ) = N ∪ Σ ∪ { → $N$$\Sigma$$N \times (N\cup \Sigma )^*$$R_{(N,\Sigma)} = N \cup \Sigma \cup \{\rightarrow\}$$G = (N, \Sigma, R, S)$

• $N$ est un ensemble fini de non terminaux
• $\Sigma$ est un alphabet fini
• $R$ est un ensemble de règles de la forme $A \rightarrow w$ avec $A \in N$ , $w \in (N \cup \Sigma)^*$ telle sorte qu'il y a du CFG $G'$ sur $R_{(N,\Sigma)}$ avec $R = L(G')$
• $S \in N$ est le non terminal initial

et nous définissons $L(G)$ pour de tels CFG à règles infinies comme pour les CFG, quelle est la relation entre la classe de langages générée par les CFG à règles infinies (appelons cette classe $irCF$ ), la classe des langages sans contexte $CF$ et la classe $RE$ ?

De toute évidence, nous avons , mais est- équivalent à l'une de ces classes (ou à une autre classe)?i r C $CF \subseteq irCF \subseteq RE$$irCF$

Supposons que nous prenons le métagramme et le factorisons par des préfixes à deux symboles. En d' autres termes, pour chaque construction , le dérivé de gauche de au-dessus de la chaîne . Cela produira un (fini) de (finis) metagrammars, chacun produisant toutes les productions (peut - être infini) pour certains . A ∈ N G ′ A G ′ A → A ∈ $G'$$A \in N$$G'_A$$G'$$A \to$$A \in N$

Maintenant, construisons la grammaire , dont les règles sont l'union de toutes les règles dans les grammaires (avec des non-terminaux renommés pour éviter les collisions), ainsi que pour chaque , où est le non-terminal de pour . Les non-terminaux pour comprennent et tous les non-terminaux pour chaque ; le non-terminal départ est le non-terminal de départ , et les bornes de sont précisément les bornes . J'affirme (sans preuve) que$G''$$G'_A$$A \to S_{G'_A}$$G'_A$$S_{G'_A}$$G'_A$$G''$$N$$G'_A$$G$$G''$$G$$G''$est une grammaire finie pour la même langue, car le processus de dérivation n'est pas affecté par l'origine des règles; c'est juste une substitution de chaîne sur un alphabet.

Si le contour de preuve ci-dessus est valide, et sont identiques.$CF$$irCF$

Comme je l'ai mentionné dans un commentaire, il existe des exemples plus intéressants de grammaires à deux niveaux, y compris les grammaires Van Wijngaarden et les diverses tentatives qui ont été faites pour créer des formalismes plus faciles à gérer sans perdre tout le pouvoir supplémentaire.