szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 19 maja 2017, o 16:50 
Użytkownik

Posty: 1
Lokalizacja: Polska
Cześć,
jestem w trakcie robienia zadania i chciałbym się upewnić czy dobrze mi wyszło. Mam następujące reguły produkcji:
$ 
\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:
$ 
\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*} $

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:
((((zy + yxz + xz) z + y) x^{m} ) z ) z^{n}

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

Więc otrzymałem:

$ 
\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 Y \to XZ | XA | y zamiast Y \to XZ|YA|y
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Algorytmy] CYK, postać normalna Chomsky'ego  przem11122  0
 [C++] Program wypisujacy lancuchy dla gramatyki  yamatano18  0
 [Gramatyki] Podaj gramatykę generującą język - zadanie 2  brit16  0
 [Gramatyki] Parser LALR  pioter-b  0
 [Gramatyki] Lemat o pompowaniu  turson  22
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl