[ Pobierz całość w formacie PDF ]

S
a S
A
a
S A
b
b a
a
RYS. 5.1. Drzewo wyprowadzenia dla przykładu 1.
66
Dwa drzewa wyprowadzeń są to\samościowo równe, je\eli posiadają taką samą
strukturę gałęzi oraz są zaopatrzone w jednakowe etykiety przy tych samych węzłach. Liczba
reguł jest skończona, natomiast liczba znaczników mo\e być nieskończona, wówczas mogą
istnieć takie symbole alfabetu pomocniczego, które powtarzają się w znacznikach struktury
dowolną ilość razy. Dodatkowo, mogą istnieć takie łańcuchy drzewa, które zawierają pewien
symbol więcej ni\ n razy dla dowolnego z góry ustalonego n.
Dla zdefiniowania języka generowanego przez gramatykę G =
wprowadzmy notację do reprezentowania wyprowadzeń. Pierwszym krokiem będzie
*
zdefiniowanie dwóch relacji wyprowadzenia. Ò!G i Ò!G Relacje te Å‚Ä…czÄ… dwa Å‚aÅ„cuchy słów
utworzonych z symboli pomocniczych lub symboli koÅ„cowych. JeÅ›li A ² jest produkcjÄ…
z P, a symbole ± i ³ sÄ… dowolnymi symbolami z alfabetu, to mówimy,
\e ±A³ Ò!G ±²³  jest wyprowadzane.
Mówimy, \e produkcja A ² zastosowana do Å‚aÅ„cucha ±A³ daje w wyniku ±²³,
albo inaczej, \e ±²³ jest bezpoÅ›rednio wyprowadzalne z ±A³ w gramatyce G.
A ²
±, ³ " (V *" T)*  domkniÄ™cie Kleene ego
±A³Ò!G ±²³
Dwa łańcuchy są związane relacja bezpośredniej wyprowadzalności, gdy drugi z nich
mo\na otrzymać, z pierwszego poprzez zastosowanie jednej z produkcji P. Przypuśćmy, \e
±1, ±2,& ,±m sÄ… Å‚aÅ„cuchami z (V*"T)*, m e" 1, oraz ±1Ò! G ±2, ±2 Ò! G ±3, .....±m-1Ò! G ±m
wtedy piszemy:
*
±1 Ò!G ±m
i mówimy, \e ±m jest wyprowadzalne z ±1 w gramatyce G.
Przykład 2: Mamy gramatykę G=, gdzie V={S}, T={a,b}, i P={S aSb, S ab}.
Jedyną zmienną jest tu S, a i b są symbolami końcowymi. Istnieją dwie produkcje S aSb,
S ab. Stosując pierwszą z nich n-1 razy, a następnie jedną raz drugą otrzymujemy:
SÒ! aSb Ò! aaSbb Ò! a3Sb3 Ò!...Ò! an-1Sbn-1 Ò! anbn
67
5.5. Klasyfikacja Chomsky ego.
Podstawowym obiektem zastosowań teorii gramatyk nie są dowolne gramatyki, lecz
gramatyki szczególnych typów, które są najwa\niejsze zarówno z teoretycznego jaki
i praktycznego punktu widzenia. Wyró\nienia tych typów dokonuje się na podstawie postaci
reguł. W teorii Chomsky ego mo\na wyró\nić cztery typy gramatyk. Gramatyki
te wyodrębnia się poprzez nakładanie coraz silniejszych ograniczeń na układ reguł P:
gramatyka klasy 0  charakteryzuje się ona tym, \e wszystkie produkcje mają postać:
u’! u " A* = {µ }, w "A*= {µ }, gdzie A* = (V *" T)* A*  to ciÄ…g znaków
’!w,
’!
’!
pomocniczych, tworzonych na bazie słownika A = (V *" T).
gramatyka klasy 1  zwana gramatyką kontekstową, to gramatyka, która
charakteryzuje siÄ™ tym, \e wszystkie produkcje majÄ… postać: uXw ’! ubw, u,w"A*,
’!
’!
’!
A"S, X  symbol pomocniczy, b  jest elementem znaków końcowych szczególnie
gdzie b " A* \ {µ }.
gramatyka klasy 2  zwana gramatyką bezkontekstową, która w układzie reguł P
dopuszcza jedynie reguÅ‚y postaci X’!
’!b, A"S , b" A*\ {µ},
’!
’!
gramatyka klasy 3  zwana gramatyką regularną, która w układzie reguł P
dopuszcza reguły postaci:
X’!bY  gramatyki prawostronnie regularne,
X’!Yb  gramatyki lewostronnie regularne, A"S, B"S*" {µ}, b"T*\ {µ}.
Element syntaktyczny nazywany jest elementem rekursywnym, wtedy gdy
dla pewnego z góry ustalonego n istnieje takie drzewo struktury, którego łańcuch zawiera ten
symbol jako nazwę węzła więcej ni\ n razy [AAFI 77]. Zatem wyodrębnić nale\y trzy rodzaje
elementów rekursywnych:
element A nazywa siÄ™ leworekursywnym, je\eli podporzÄ…dkowane mu drzewo zawiera
A tylko w łańcuchu wysuniętym najbardziej w lewo,
element A nazywa siÄ™ praworekursywnym, je\eli podporzÄ…dkowane mu drzewo
zawiera A tylko w łańcuchu wysuniętym najbardziej w prawo,
element A nazywa siÄ™ samozanurzajÄ…cym, je\eli podporzÄ…dkowane mu drzewo
zawiera A w pewnym łańcuchu wewnętrznym.
68
A A A
B C B C B C
A A A
RYS. 5.2a RYS. 5.2b RYS. 5.2c
RYS. 5.2. Elementy rekursywne: a) leworekursywny, b) samozanurzajÄ…cy, c) praworekursywny.
69
Literatura
[AAFI 77] Zoja Ałfierowa: Teoria algorytmów. PWN, Warszawa, 1977.
[HARE 92] Dawid Harel: Rzecz o istocie informatyki. WNT, Warszawa, 1992.
[HOPC 94] John E. Hopcroft, Jefrey D. Ullman :Wprowadzenie do teorii automatów,
języków i obliczeń. PWN, Warszawa, 1994.
[TURS 77] Władysław M.Turski: Propedeutyka informatyki. PWN, Warszawa, 1977.
[KOZI 94] Stanisław Kozielski: Zbiór zadań z podstaw informatyki. Politechnika
ZlÄ…ska-Skrypt uczelniany nr 1842, Gliwice, 1994.
[POCH 94] B. Pochopień: Arytmetyka systemów cyfrowych. Skrypt Politechniki
ZlÄ…skiej, nr 1841, Gliwice, 1994.
[KENN 03] Kenneth A. Ross, Charles R. B. Wright Matematyka dyskretna.
Wydawnictwo Naukowe PWN, Warszawa 2003.
[KEAT 03] Jody Keating: FLASH MX Vademecum profesjonalisty Helion, Gliwice
2003.
[REIN 04] Robert Reinhardt, Snow Dow Flash MX 2004. Biblia Helion Gliwice 2004 [ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • angela90.opx.pl

    • Archiwum