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

9

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ęzykL nad jakimś alfabetem Σ może być opisany przez CFG G=({S},Σ,R,S) z R={SwwL}. Ale co jeśli ograniczymyR do takich zestawów reguł, które mogą być tworzone przez gramatyki bezkontekstowe?

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

  • N jest skończonym zestawem nieterminali
  • Σ jest skończonym alfabetem
  • R jest zbiorem reguł formularza Aw z AN, w(NΣ) tak, że jest trochę CFG G nad R(N,Σ) z R=L(G)
  • SN 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 CFirCFRE, ale jest irCF równoważne jednej z tych klas (lub innej klasie)?

miernik
źródło

Odpowiedzi:

7

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

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), żeGAASGAGASGAGAGNGAGGGGjest 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.CFirCF

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.

rici
źródło