WDI

[ 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 ]

Archiwum

Drogi użytkowniku!