95999

Powyższa definicja nie jest ukierunkowana jedynie na gramatyki bezkontekstowe, ale w wyprowadzeniu lewostronnym w gramatyce bezkontekstowej zawsze skrajny lewy nieterminal jest zastępowany prawą stroną pewnej produkcji

Forma zdaniowa 1/ jest wyprowadzalna bezpośrednio prawostronnie z formy zdaniowej co w gramatyce G, co zapisujemy

Cl) =>GP V

jeżeli:

0) =*G V ea = ya8 V = y(58 (a -» p) e P Se T’

a, p, Y, V, o e (NuT)'

Podobnie jak poprzednio, powyższa definicja nie jest ukierunkowana jedynie na gramatyki bezkontekstowe, ale w wyprowadzeniu praw'Ostronnynr w gramatyce bezkontekstowej zawsze skrajny prawy nieterminal jest zastępowany prawą stroną pewnej produkcji.

Podobnie jak poprzednio, definiuje się relacje =»gi⁺, =>gl =»op*, =>op\ które są odpowiednio przechodnim oraz przechodnim i zwrotnym domkraęciem relacji bezpośredniej wyprowadzalności lewostronnej =>_Gl 1 prawostronnej =?_<IF Jeżeli wiadomo, o jaką gramatykę chodzi, pomijamy dolny indeks „G” w oznaczeniu tych relacji pisząc po prostu: =>l*, =>l , =>r*, =>p , =>l oraz =>p

Przykład:

Niech będzie dana gramatyka bezkontekstowa G = <N, T, P, Z>, gdzie:

N = {E, T, F}

T = {a, +, *,(,)}

P = { E -» E+T | T T -»T*F | F F -> (E) | a

}

Z = E

Formą zdaniową w tej gramatyce jest np. łańcuch: a+F*T

gdyż:

E => E+T => T+T => F+T => a+T => a+T*F Po)vyższe wyprowadzenie polegało na każdor azowym zastępowaniu skrajnego lewego nieterminala prawą stroną jakiejś odpowiedniej produkcji, więc każdy' krok tego wyprowadzenia jest wyprowadzeniem lewostronnym Możemy więc powiedzieć, że rozpatrywany łańcuch jest fonną zdaniową wyprowadzalną lew'ostronnie.

E E+T =>l T+T =>1 F+T ^a+T =)>I a+T^łF Spróbujmy wyprowadzić badany łańcuch prawrostronnie:

E =>_P E+T =>_P E+T*F