[Gramatyki] Wyznaczenie języka dla danej gramatyki

[dall]

Hej
Mam problem w zadaniu w którym z podanej gramatyki bezkontekstowej mam wyprowadzić język generowany przez nią. Niestety zawsze gubię się i za każdym razem wychodzą mi różne rzeczy :/ Czy ktoś mógłby mi to rozpisać?
\(\displaystyle{ G=\left\langle \{S,Y,X,Z,y,x,z\},\{y,x,z\},P,S\right\rangle}\)
reguły produkcji:
\(\displaystyle{ S \rightarrow SZ|Y\\
Y \rightarrow YX|z\\
X \rightarrow Zy|x\\
Z \rightarrow y|z}\)

Mam to rozwiązać do końca tygodnia ale wolę zapytać wcześniej niż później zostawić to sobie na sam koniec. Z góry dziękuję za każdą pomoc

EDIT:
Moje ostatnie dwa rozwiązania:
\(\displaystyle{ z((y+z)y+x)^m(y+z)^n+z(y+z)^n\\}\)
I drugie (to wyszło mi dwa razy takie samo, więc pewnie coś jest na rzeczy )
\(\displaystyle{ z+z((y+z)y+x)^m+z(y+z)^n+z((y+z)y+x)^m(y+z)^n}\)
Wszystkie współczynniki (chyba) od 0...
Czy ktoś może mi powiedzieć czy któreś z tych rozwiązań jest dobre? A jeśli jest jakiś błąd to gdzie?

[norwimaj]

Oba Twoje wyniki są takie same, a jeszcze krócej można to zapisać tak: \(\displaystyle{ z((y+z)y+x)^m(y+z)^n,}\) albo raczej tak: \(\displaystyle{ z((y+z)y+x)^{\ast}(y+z)^{\ast}.}\) Ten język jest regularny.

[dall]

@up mógłbyś podać przykład 5-literowego słowa? (czy np. zyyxy będzie czy raczej nie?) Bo kolejnym 'punktem' zadania jest algorytm Cocke'a-Youngera-Kasamiego dla dowolnego 5-literowego słowa. Jestem zielona z tego więc wolę zapytać
Dzięki wielkie za dotychczasową pomoc

[norwimaj]

Tak, to słowo należy do języka.

\(\displaystyle{ \overbrace{\overbrace{\overbrace{\overbrace{\overbrace{z}^Y \overbrace{\overbrace{y}^Z y}^X}^Y \overbrace{x}^X}^Y}^S \overbrace{y}^Z}^S}\)

[dall]

A jakiś pomysł czemu mi nie wychodzi z algorytmu Cocke'a-Youngera-Kasamiego?

[norwimaj]

A czy przekształciłaś tę gramatykę do postaci normalnej Chomsky'ego?

[dall]

Tak, chyba że tutaj popełniłam błąd. Powinno być tak?
\(\displaystyle{ S \rightarrow SZ|YX|z\\
Y \rightarrow YX|z\\
X \rightarrow ZA|x\\
Z \rightarrow y|z\\
A \rightarrow y}\)

Nie jestem pewna czy potrzebne sa nam teraz reguły \(\displaystyle{ Y \rightarrow YX|z\\}\) ale czy je odrzucę czy zostawię to i tak nic dobrego mi nie wychodzi

[norwimaj]

Nie jestem pewna czy potrzebne sa nam teraz reguły \(\displaystyle{ Y \rightarrow YX|z\\}\)

Raczej tak.


Wypełniłem wiersze tabeli odpowiadające podsłowom długości \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\). Do tej pory masz tak samo? Co dalej?
\(\displaystyle{ \begin{array}{l|c|c|c|c|c}
& z & y & y & x & y \\
1 & S,Y,Z & Z,A & Z,A & X & Z,A \\
2 & S,X & X & & & \\
\end{array}}\)

[dall]

A dalej nic mi nie wychodzi niestety. Nie ma reguły która po prawej stronie ma ZX lub AZ (podobnie dalej, nie ma XZ ani XA), a w 3. wierszu nie ma SX ani XX

EDIT:
Już rozumiem błąd, biorę tylko tak jakby jeden przypadek...
\(\displaystyle{ 3\ |\ Y,S\ |\ -\ |\ -\ |\\
4\ |\ S\ |\ -\ |\\
5\ |\ S\ |}\)
Czyli wychodzi na to że pośrednio z symbolu początkowego można otrzymać słowo zyyxy.

Dzięki wielkie za pomoc

[norwimaj]

Dla słowa \(\displaystyle{ zyyx}\) (\(\displaystyle{ 4.}\) wiersz) jest nie tylko \(\displaystyle{ S,}\) ale też \(\displaystyle{ Y,}\) bo mamy produkcję \(\displaystyle{ Y\to YX.}\) (podział \(\displaystyle{ zyy\cdot x}\))