[ 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 =
wprowadz
my 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 [AA
FI 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
[AA
FI 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
Z
ląska-Skrypt uczelniany nr 1842, Gliwice, 1994.
[POCH 94] B. Pochopień: Arytmetyka systemów cyfrowych. Skrypt Politechniki
Z
lą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 ]

• Start
• Zmagania o reformę. Z dziennika politycznego 1980 1990
• Jelenska Emma Obraczka
• Machiavelli Ksić…śźe
• Quinnell A.J Pieklo (pdf)
• Nicholas Sparks Noce w Rodanthe
• 344. DUO Philips Sabrina Kaprys milionera
• Charmed 07 Zirkuszauber Frauke Meier
• 0747. Gold Kristi Pokochać króla
• Brian KateMegan Przewodnik Po ChśÂ‚opcach(1)
• 338. Brooks Helen śÂšwić™ta nad Tamizć…
• zanotowane.pl
• doc.pisz.pl
• pdf.pisz.pl
• prymasek.xlx.pl