Oto pytanie z książki Dragon (przepraszam za błędy w tłumaczeniu, nie mam pod ręką wersji angielskiej):
Jaki język jest generowany przez tę gramatykę?
Nie wiem, co mam tutaj robić. Definicja w książce o językach mówi to (i to w zasadzie w rozdziale):
język jest zbiorem wszystkich słów, które mogą być tworzone przez dowolne drzewo analizy.
Tak więc, jeśli chcę zrobić „dowolne” drzewo parsowania z tej gramatyki, mogę rekurencyjnie je budować, używając tylko dwóch pierwszych reguł. Szukałem trochę i mam wrażenie, że każdą zasadę trzeba zastosować raz, ale nie jestem pewien. Byłoby bardzo pomocne, gdyby ktoś był w stanie udzielić wskazówek na temat rozwiązywania tego rodzaju problemów.
Odpowiedzi:
Podpowiedź: Co można powiedzieć o liczbie s a s produkowane w słowach?a b
Nie ma tutaj jednego uniwersalnego przepisu. Zasadniczo nie można rozstrzygnąć, czy dwa CFG wytwarzają ten sam język, czy dwa CFL są tym samym językiem. Przydatną metodą jest próba zauważenia właściwości, które pozostają niezmienne podczas produkcji.
źródło
Wskazówka: Zbuduj kilka słów generowanych przez tę gramatykę. Czy widzisz wzór? Czy potrafisz opisać niektóre właściwości wszystkich słów generowanych przez gramatykę, po prostu patrząc na reguły? Kiedy już odgadniesz (poprawnie) język generowany przez gramatykę, nie będzie to trudne do udowodnienia.
źródło