Jak potężne są CFG, które pozwalają na nieskończoną liczbę zasad?

Zastanawiałem się ostatnio, co by się stało, gdybyśmy pozwolili gramatykom bezkontekstowym mieć nieskończoną liczbę reguł. Oczywiście, gdybyśmy zezwolili na arbitralne takie nieskończone zbiory reguł, każdy język$L$ nad jakimś alfabetem $\Sigma$ może być opisany przez CFG $G = (\{S\},\Sigma,R,S)$ z $R = \{S \rightarrow w \mid w \in L \}$. Ale co jeśli ograniczymy$R$ do takich zestawów reguł, które mogą być tworzone przez gramatyki bezkontekstowe?

W tym celu podano zestaw nieterminali $N$ i terminale $\Sigma$, zobaczmy reguły nie jako elementy $N \times (N\cup \Sigma )^*$, ale jako ciągi znaków nad alfabetem $R_{(N,\Sigma)} = N \cup \Sigma \cup \{\rightarrow\}$. Teraz moje pytanie brzmi: jeśli zdefiniujemy nieskończoną regułę CFG jako krotkę$G = (N, \Sigma, R, S)$ gdzie

• $N$ jest skończonym zestawem nieterminali
• $\Sigma$ jest skończonym alfabetem
• $R$ jest zbiorem reguł formularza $A \rightarrow w$ z $A \in N$, $w \in (N \cup \Sigma)^*$ tak, że jest trochę CFG $G'$ nad $R_{(N,\Sigma)}$ z $R = L(G')$
• $S \in N$ jest początkowym nieterminalnym

i my definiujemy $L(G)$ dla takich nieskończonych CFG z regułami, tak jak ma to miejsce w przypadku CFG, jaka jest relacja między klasą języków generowanych przez nieskończone CFG z regułami (nazwijmy tę klasę $irCF$), klasa języków bezkontekstowych $CF$ i klasa $RE$?

Oczywiście, że mamy $CF \subseteq irCF \subseteq RE$, ale jest $irCF$ równoważne jednej z tych klas (lub innej klasie)?

Załóżmy, że bierzemy metagrammar $G'$i podzielmy to na dwa przedrostki. Innymi słowy, dla każdego$A \in N$ skonstruować $G'_A$, lewostronna pochodna $G'$ nad sznurkiem $A \to$. To stworzy (skończony) zestaw (skończonych) metagramatów, z których każda produkuje wszystkie (być może nieskończone) produkcje dla niektórych$A \in N$.

Teraz zbuduj gramatykę $G''$, którego reguły są wszystkich reguł w gramatyce (z nie-terminali, aby uniknąć kolizji), wraz z dla każdego , gdzie jest początkowym non-terminalem dla . dla obejmują i wszystkie nieterminale dla każdego ; początek nieterminalny jest początek niż zacisk i zaciski dla są dokładnie zaciski . Zapewniam (bez dowodu), że$G'_A$$A \to S_{G'_A}$$G'_A$$S_{G'_A}$$G'_A$$G''$$N$$G'_A$$G$$G''$$G$$G''$jest skończoną gramatyką dla tego samego języka, ponieważ pochodzenie reguł nie ma wpływu na proces wyprowadzania; jest to tylko zamiana ciągu na alfabet.

Jeśli powyższy zarys dowodu jest prawidłowy, i są takie same.$CF$$irCF$

Jak wspomniałem w komentarzu, istnieją bardziej interesujące przykłady gramatyki dwupoziomowej, w tym gramatyki Van Wijngaarden i różne próby, które podjęto, aby stworzyć łatwiejsze do opanowania formalizmy bez utraty dodatkowej mocy.