Witam, mam pewną zagwozdkę.
Umiem rozpisać całą produkcję Chomsky'ego w krokach 1-3, ale nie mam bladego pojęcia jak tworzyć skróty, które są w kroku 4.
Uważałem, że należy to robić tak aby maksymalnie zminimalizować zapis, ale byłem w błędzie.
Być może, ktoś potrafi wytłumaczyć na jakiej podstawie stwierdzić które litery należy wciągnąć w ten skrót i ile ich powinno być.
Będę mega wdzięczny
Dokładnie tak jak w przykładzie.
Postać normalna Chomskyego jest wtedy, gdy są TYLKO produkcje typu S -> AB albo S -> c (nieterminal w 2 nietermianle lub terminal)
Jeżeli masz np. produkcje S -> Ab | c to musisz przekształcić to do postaci S -> AB|C, B -> B.
Czyli prościej mówiąc dodajesz kolejną produkcję typu X -> YZ lub A -> a dopóki wszystkie produkcje gramatyki nie będą miały takiej formy.
Yurati napisał(a):
Dokładnie tak jak w przykładzie.
Postać normalna Chomskyego jest wtedy, gdy są TYLKO produkcje typu S -> AB albo S -> c (nieterminal w 2 nietermianle lub terminal)
Jeżeli masz np. produkcje S -> Ab | c to musisz przekształcić to do postaci S -> AB|C, B -> B.
Czyli prościej mówiąc dodajesz kolejną produkcję typu X -> YZ lub A -> a dopóki wszystkie produkcje gramatyki nie będą miały takiej formy.
Tak to umiem, ale nie potrafię kroku 4. Tam są skróty zaznaczone na brązowo konkretnie chodzi mi o:
Tworzymy produkcje postaci: X→ Z1Z2 (n=2) lub X→t:
P4 = { S → AR1 |AX | YB|b |a; X→ BR2 |YB |BA |BR4 |BR3 ; Y→ YB|b ; A→a; B→b
R1→AS; R2→XR3; R3→ AX; R4→ XA }
Vejmal napisał(a):
Yurati napisał(a):
Dokładnie tak jak w przykładzie.
Postać normalna Chomskyego jest wtedy, gdy są TYLKO produkcje typu S -> AB albo S -> c (nieterminal w 2 nietermianle lub terminal)
Jeżeli masz np. produkcje S -> Ab | c to musisz przekształcić to do postaci S -> AB|C, B -> B.
Czyli prościej mówiąc dodajesz kolejną produkcję typu X -> YZ lub A -> a dopóki wszystkie produkcje gramatyki nie będą miały takiej formy.Tak to umiem, ale nie potrafię kroku 4. Tam są skróty zaznaczone na brązowo konkretnie chodzi mi o:
Tworzymy produkcje postaci: X→ Z1Z2 (n=2) lub X→t:
P4 = { S → AR1 |AX | YB|b |a; X→ BR2 |YB |BA |BR4 |BR3 ; Y→ YB|b ; A→a; B→b
R1→AS; R2→XR3; R3→ AX; R4→ XA }
Zauważ, że w kroku 3. zostaje Ci np. S->AAS|AX|YB|b|a. Produkcja S->AAS nie jest w postaci normlanej, więc aby ją przekształcić do tej postaci dodajemy produkcje R -> AS (która jest w postaci normalnej), a w S ->AAS zastępujemy AS produkcją R i otrzymujemy S->AR, która jest w postaci normalnej. Analogicznie reszta
Polecam http://kompilatory.agh.edu.pl/index.php?menu=automaty zarówno wykłady jak i zadania+odpowiedzi
Ja z kolei polecę ten skrypt:
https://www.mimuw.edu.pl/~szymtor/jao/skrypt.pdf
chyba w ogóle wrzucam tę rekomendację, bo spojrzałem na slajdy od @Shalom i źle mi się zrobiło od tych zapisów matematycznych składanych w Power Poincie
Yurati napisał(a):
Vejmal napisał(a):
Yurati napisał(a):
Dokładnie tak jak w przykładzie.
Postać normalna Chomskyego jest wtedy, gdy są TYLKO produkcje typu S -> AB albo S -> c (nieterminal w 2 nietermianle lub terminal)
Jeżeli masz np. produkcje S -> Ab | c to musisz przekształcić to do postaci S -> AB|C, B -> B.
Czyli prościej mówiąc dodajesz kolejną produkcję typu X -> YZ lub A -> a dopóki wszystkie produkcje gramatyki nie będą miały takiej formy.Tak to umiem, ale nie potrafię kroku 4. Tam są skróty zaznaczone na brązowo konkretnie chodzi mi o:
Tworzymy produkcje postaci: X→ Z1Z2 (n=2) lub X→t:
P4 = { S → AR1 |AX | YB|b |a; X→ BR2 |YB |BA |BR4 |BR3 ; Y→ YB|b ; A→a; B→b
R1→AS; R2→XR3; R3→ AX; R4→ XA }Zauważ, że w kroku 3. zostaje Ci np. S->AAS|AX|YB|b|a. Produkcja S->AAS nie jest w postaci normlanej, więc aby ją przekształcić do tej postaci dodajemy produkcje R -> AS (która jest w postaci normalnej), a w S ->AAS zastępujemy AS produkcją R i otrzymujemy S->AR, która jest w postaci normalnej. Analogicznie reszta
Dzięki, rada dot. nieterminali/terminali pomogła :)
Póki jeszcze temat jest otwarty, pozwolę sobie zadać pytanie
G = ({S}, {a, b}, { S ⟶ XYZ, X⟶bXXa | λ, Y⟶bbY | b, Z⟶ Za | λ }, S).
G = ({S}, {a, b}, { S ⟶ XY| Z, X⟶bXXa | λ, Y⟶bbY | b, Z⟶ Za | λ }, S).
Czy w tych przypadkach muszę rozbić XYZ / XY|Z - > bXXa | bbY | Za (no i I krok produkcji zastosować, pisałem skrótowo) czy po prostu zostawić i w IV kroku streścić to?