Znalezienie języka generowanego przez gramatykę bezkontekstową

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ę?

$S \rightarrow a S b S \mid b S a S \mid \epsilon$

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.

formal-languages context-free formal-grammars

— dan
źródło

Wskazówka: użyj wyrażenia regularnego

— Bartosz Przybylski

Aby uzyskać wskazówki, zobacz odpowiedzi poniżej. W odpowiedzi na twoje pytanie: nie, nie musisz używać każdej reguły co najmniej raz. Zacznij od symbolu początkowego (lub aksjomatu) i stosuj reguły przepisywania, aż pozostaną same symbole terminali (tutaj małe litery).

— Hendrik Jan

zakładając, że pusty Ciąg nie jest Symbolem końcowym, w moim rozumieniu nie jest możliwe, aby pozostały tylko symbole końcowe, czy też coś nie rozumiem?

— dan

Crossposted na cs.SE .

— Raphael

@dan. Pusty ciąg zniknie, więc możesz skończyć tylko z terminalami: . Na przykład.

S \Rightarrow a S b S \Rightarrow a a S b b S \Rightarrow a a b b S \Rightarrow a a b b b S a \Rightarrow a a b b b a

$S \Rightarrow aSbS \Rightarrow aaSbbS \Rightarrow aabbS \Rightarrow aabbbSa \Rightarrow aabbba$

— Hendrik Jan

Odpowiedzi:

Podpowiedź: Co można powiedzieć o liczbie s a s produkowane w słowach? $a$ $b$

Byłoby bardzo pomocne, gdyby ktoś był w stanie udzielić wskazówek na temat rozwiązywania tego rodzaju problemów.

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.

— Mnie.
ź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.

— Yuval Filmus
źródło