9752257319

Wykład 1, str. 10

[ja^^mmatyk^jefinkjj^ęzyk?J

DEFINICJA: Wywodliwość —

•    jeśli w P jest produkcja A —> w, to dla dowolnych słów

u, v £ (N U E)*, słowo uwv nazywamy bezpośrednio wywodliwym ze słowa uAv, co oznaczamy uAv =>g uwv\

•    jeśli w\ =>g ^w2< u>2 =^g ^w3.....wj_n—i =>g ^wn, to słowo nazywamy

wywodliwym ze słowa Wi, co oznaczamy W\ =^g Wn-

DEFINICJA: Język L(G) generowany przez gramatykę G —

składa się z tych słów wywodliwych z aksjomatu, które już nie zawierają

nieterminali: L(G) = jtu E E* | S    }.

Przykład:

Gramatyka:    A —» A

A —> aAa A —» bAb

A =>* bbaabb E L(G)

Fakt:

L(G) = {ww^R\we{a,b}*}

A =$■ bAb =>• bbAbb => bbaAabb => bbaabb

Jak gramatyka definiuje języl^	Wykład 1, str. 11
NIE MYLIĆ:		A —> X A -» OAl

—»    — formalny symbol w produkcji w gramatyce

=>•    —■ relacja bezpośredniej wywodliwości:

jeśli A —> w to A w ale np. 0A1 => 00A11 a nieprawda, że OAl —> 00A11

=>* — relacja wywodliwości:

jeśli W\ => W2 to W\ =$>* W2 ale np. A =>-*0011 a nieprawda, że A =>■ 0011