Witam :)
Prosta fraza formy zdaniowej s=aba dla pewnego symbolu terminalnego A nazywamy ciąg b, jeżeli S=>*aAa(część wspólna)A->b należy do P. Uchwyt to najbardziej na lewo prosta fraza. Czy ktoś wie co to jest, lub rozumie tę definicje?
0
0
Tak. Ten "uchwyt" nazywa się też czasem osnową. Narysuj sobie rozkład zadanej formy zdaniowej. Frazą prostą jest każda wartość "liścia" tego drzewka która ma nad sobą pojedynczy nieterminal (który nie ma żadnego "rozwidlenia"). Osnową jest skrajnie lewa fraza prosta. Żeby wypisać wszystkie frazy należy wypisywać wartości liści dla każdego nieterminala.
Weźmy np. gramatykę
S -> aAa
A -> b
i frazę aba. Drzewko wygląda tak:
S
/ | \
a A a
|
b
Jak widać jedyną frazą prostą jest b, jest ono też osnową. Pozostałe frazy to: aba (dla nieterminala S)
(mogłem coś pochrzanić :P)
Jeśli masz z tym problem to polecam wykłady z Teorii Automatów i Języków formalnych: http://kompilatory.agh.edu.pl/