[Gramatyki] Wyprowadzenie, przekształcenie do Chomsky'ego

kubas246
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 19 maja 2017, o 16:00
Płeć: Mężczyzna
Lokalizacja: Polska

[Gramatyki] Wyprowadzenie, przekształcenie do Chomsky'ego

Post autor: kubas246 »

Cześć,
jestem w trakcie robienia zadania i chciałbym się upewnić czy dobrze mi wyszło. Mam następujące reguły produkcji:
\(\displaystyle{ $
\setlength{\arraycolsep}{2pt}
\begin{array}{lcccccc}
S & \to & YZ & | & SZ & | & z \\
Y & \to & Xz & | & Yx & | & y \\
X & \to & Zy & | & yxz & | & xz \\
Z & \to & z
\end{array} $}\)


Wyprowadziłem język tak:
\(\displaystyle{ $
\begin{align*}
S & \longrightarrow^2 SZ \longrightarrow^{*2} SZ^{n} \longrightarrow^{1,3} (YZ+z)Z^{n} \longrightarrow^{10} (Yz+z)z ^{n} \\
& \longrightarrow ^{*5} ((Yx^{m})z+z)z^{n} \longrightarrow^{4,6} (((Xz+y)x^{m})z+z)z^{n} \\
& \longrightarrow ^{7,8,9} ((((Zy + yxz +xz)z+y)x^{m})z+z)z^{n} \\
& \longrightarrow ^{10} ((((zy + yxz + xz) z + y) x^{m} ) z + z ) z^{n}
\end{align*} $}\)


\(\displaystyle{ m = 0, 1 \ldots \\
n = 0, 1 \ldots}\)


Z czego jak rozumiem można to z + z uprościć do po prostu z i ostatecznie mam:
\(\displaystyle{ ((((zy + yxz + xz) z + y) x^{m} ) z ) z^{n}}\)

Następnie przekształciłem to tak do postaci Chomsky'ego:
\(\displaystyle{ Y \to Xz}\) w \(\displaystyle{ Y \to XZ}\)
\(\displaystyle{ Y \to Yx}\) w \(\displaystyle{ Y \to XA}\) i \(\displaystyle{ A \to x}\)
\(\displaystyle{ X \to Zy}\) w \(\displaystyle{ X \to ZB}\) i \(\displaystyle{ B \to y}\)
\(\displaystyle{ X \to yxz}\) w \(\displaystyle{ X \to BAZ}\) w \(\displaystyle{ X \to CZ}\) i \(\displaystyle{ C \to BA}\)
\(\displaystyle{ X \to xz}\) w \(\displaystyle{ X \to AZ}\)

Więc otrzymałem:

\(\displaystyle{ $
\setlength{\arraycolsep}{2pt}
\begin{array}{lcccccc}
S & \to & YZ & | & SZ & | & z \\
Y & \to & XZ & | & XA & | & y \\
X & \to & ZB & | & CZ & | & AZ \\
Z & \to & z \\
A & \to & x \\
B & \to & y \\
C & \to & BA
\end{array} $}\)


Mógłby ktoś potwierdzić czy dobrze?

EDIT:
Dobra, coś mam źle na 100% bo mi w algorytmie C-Y-K wychodzą bzdury. Ktoś jest w stanie wskazać mi gdzie mam błąd?
EDIT2:
Temat do zamknięcia, po przerwie wróciłem do zadania i widzę, że przecież mam w postaci Chomskey'ego wrzucone \(\displaystyle{ Y \to XZ | XA | y}\) zamiast \(\displaystyle{ Y \to XZ|YA|y}\)
Ostatnio zmieniony 20 maja 2017, o 17:42 przez Afish, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
ODPOWIEDZ