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 nad jakimś alfabetem może być opisany przez CFG z . Ale co jeśli ograniczymy do takich zestawów reguł, które mogą być tworzone przez gramatyki bezkontekstowe?
W tym celu podano zestaw nieterminali i terminale , zobaczmy reguły nie jako elementy , ale jako ciągi znaków nad alfabetem . Teraz moje pytanie brzmi: jeśli zdefiniujemy nieskończoną regułę CFG jako krotkę gdzie
- jest skończonym zestawem nieterminali
- jest skończonym alfabetem
- jest zbiorem reguł formularza z , tak, że jest trochę CFG nad z
- jest początkowym nieterminalnym
i my definiujemy 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ę ), klasa języków bezkontekstowych i klasa ?
Oczywiście, że mamy , ale jest równoważne jednej z tych klas (lub innej klasie)?
Odpowiedzi:
Załóżmy, że bierzemy metagrammarG′ i podzielmy to na dwa przedrostki. Innymi słowy, dla każdegoA∈N skonstruować G′A , 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órychA∈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), żeG′A A→SG′A G′A SG′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.
źródło