[Gramatyki] Problem z rekurencją w gramatyce bezkontekstowej

[xyo]

Witam.
Od kilku dni bezskutecznie próbuję znaleźć jakiegokolwiek rozwiązania podobnego problemu. Otóż mam takie reguły produkcji w gramatyce bezkontekstowej:
\(\displaystyle{ S \rightarrow b \\
S \rightarrow aSaS}\)

Kilka przykładowych słów:
\(\displaystyle{ b\\
a b a b\\
a b a a b a b\\
a a b a b a b\\
a b a a b a a b a b\\
a b a a a b a b a b\\
a a b a b a a b a b\\
a a b a a b a b a b\\
a a a b a b a b a b\\
a b a a b a a b a a b a b\\
a b a a b a a a b a b a b\\
a b a a a b a b a a b a b\\
a b a a a b a a b a b a b\\
a b a a a a b a b a b a b\\
a a b a b a a b a a b a b\\
a a b a b a a a b a b a b\\
a a b a a b a b a a b a b\\
a a b a a b a a b a b a b\\
a a b a a a b a b a b a b\\
a a a b a b a b a a b a b\\
a a a b a b a a b a b a b\\
a a a b a a b a b a b a b\\
a a a a b a b a b a b a b}\)

Rozumiem że w takim przypadku można zamieniać \(\displaystyle{ S}\), na '\(\displaystyle{ b}\)' lub '\(\displaystyle{ abab}\)' w dowolnej konfiguracji w każdym kroku rekurencji, ale nie potrafię opisać tego wzorem. Doszedłem do czegoś takiego
\(\displaystyle{ b + a^{n}b(ab)^{n} + (aba)^{m}b \\
n,m=0,1,..}\)
ale to zgadza się tylko z 4 pierwszymi wyrazami, a dla dalszych kroków rekurencji gubi wyrazy...
Czy mógłby mi ktoś wytłumaczyć, czy da się to zrobić, a jeśli da, to jak?

[Afish]

To najpierw pokaż czy ta gramatyka jest regularna.

[xyo]

Myślałem, że każdą g. bezkontekstową można opisać za pomocą wzoru

Więc inaczej... Jeśli na wejściu wprowadzam zbiór reguł gramatyki bezkontekstowej, a na wyjściu mam wygenerować wzór dla języka, to muszę najpierw sprawdzić czy jest to gramatyka regularna, tak?

W sumie ułatwiłoby mi to robotę, bo pojedyncze rekurencje w regułach to nie problem, a od 2 dni walczę z wielokrotnymi, jak w tym przykładzie. A najwidoczniej walczyłem z wiatrakami... :v

Tylko to wydaje mi się dziwne, bo np. w gramatyce tylko bezkontekstowej, ale nie regularnej:
\(\displaystyle{ S \rightarrow aSb | c}\)
można bez problemu wyprowadzić wzór:
\(\displaystyle{ a^{n}cb^{n} , n=0,1,...}\)

Zatem czy istnieje możliwość rozpoznania po samych regułach (po uprzednim usunięciu r. niepotrzebnych i cykli) czy istnieje wzór opisujący dany język?

[Afish]

Nie wiem, czy da się zapisać każdą bezkontekstową jako wzorek. Nie kojarzę dowodu, ale kompilatorów uczyłem się kilka lat temu, więc z pewnością moja wiedza nie jest pierwszej świeżości. Niemniej jeżeli nie jesteś w stanie pokazać, że gramatyka jest regularna, to ja nie znam innej metody niż zgadywanie.

[xyo]

Problem rozwiązany. Gramatykę tego typu można opisać wzorem z sumą, a mianowicie