WDI

[ Pobierz całość w formacie PDF ]

Słowo: 010001111
Droga akceptacji: q0,q1,q2,q8,q2,q8,q2,q8,q2,q3,q6,q7,q5,q8,q9,A
Słowo: 011
Droga akceptacji: q0,q1,q2,q3,q5,q8,q9,A.
4.4. Konstruktory.
Konstruktory diagramów przejść są to gotowe wyra\enia regularne, które umo\liwiają
stworzenie pewnego mechanizmu automatu skończonego dla dowolnego wyra\enia [HOPC
94]. Mo\na wyró\nić trzy takie postacie wyra\eń regularnych:
suma teoriomnogościowa r = r1 + r2
zło\enie r = r1 r2
domknięcie r = r1*
59
I. Konstruktor diagramu przejść dla sumy teoriomnogościowej r= r1+r2
� �
q1 f1
qo fo
q2 f2
� �
RYS. 4.9. Konstruktor diagramu przejść dla sumy teoriomnogościowej.
Zarówno pierwsza, jaki i druga droga w zaprezentowanym diagramie automatu
rozpoczyna się od przejścia do stanu q1 lub do stanu q2 przy pustym wejściu �. Jeśli droga
automatu prowadzi do q1, to w dalszym etapie mo\e dowolnie przebiegać, a\ do osiągnięcia
stanu f1, potem następuje przejście do stanu fo, przy pustym wyjściu �. Jeśli natomiast, droga
rozpoczęła się przejściem ze stanu q0 do q2 to następnie przebiega dowolną trasą,
a\ do osiągnięcia stanu f2, a następnie przechodzi do stanu f0.
II. Konstruktor dla zło\enia r = r1r2
q1 f1 q2
f2
�
RYS. 4.10. Konstruktor diagramu przejść dla zło\enia r = r1r2.
Droga z q1 do f2 w automacie składa się z drogi oznaczanej pewnym łańcuchem
x prowadzącej z q1 do f1, po której następuje przejście ze stanu f1 do stanu q2 przy pustym
wejściu � a następnie droga z q2 do f2, drogi oznaczonej pewnym łańcuchem y.
III. Konstruktor dla domknięcia r = r1*
�
� �
q0 q1 f1 f0
�
RYS. 4.11. Konstruktor diagramu przejść dla domknięcia r = r1*.
60
Droga prowadząca z q0 do f2 mo\e być dwojakiego rodzaju: albo będzie przebiegać
z q0 do f0 o etykiecie �, albo z drogi od q0 do q1 przy �, po których następuje określona liczba
(w niektórych przypadkach równie\ 0) dróg z f1 do q1. Następnie droga przebiegać będzie
przez q1 przy �, następnie znów drogą z q1 do f1, a\ w końcu drogą z f1 do f0 przy �.
Przedstawione wy\ej konstrutory będą przydatne przy tworzeniu diagramu przejść
stanów NAS dla wyra\eń regularnych. Proces ten nale\y rozpocząć od rozkładu wyra\enia
regularnego na elementarne składowe, dla których będziemy mogli tworzyć automaty,
te natomiast na podstawie konstruktorów łączymy w logiczną całość. Poni\ej zaprezentujemy
przykład automatu akceptującego wyra\enie regularne 01*+1. To wyra\enie jest postaci
r = r1 + r2 gdzie: r1=01*; r2 = 1. Dla wyra\enia r2 postać automatu jest następująca:
1
start q1 q2
RYS. 4.12.a Automat dla wyra\enia r2.
wyra\enie r1 zapiszemy jako r1 = r3 + r4 gdzie r3= 0; r4=1*. Automat dla r3 przedstawiamy
poni\ej:
start q3 q4
RYS. 4.12.b Automat dla wyra\enia r3.
następnie wyra\enie r4 mo\emy zapisać jako r4 = r*5 gdzie r5 to 1, a NAS dla r5 to:
1
start q5 q6
RYS. 4.12.c Automat dla wyra\enia r5.
Następnie powy\sze konstruktory zostaną wykorzystane dla przedstawienia automatu dla
wyra\enia r4 = 1* ( konstruktor domknięcia)
�
� �
1
start q7 q5 q6 q8
�
RYS. 4.13.a Konstruktor domknięcia.
61
Kolejno dla r1 =r3r4 (r= 01*) wykorzystujemy konstruktor zło\enia dopisując z RYS. 4.13a
rysując następującą konstrukcję:
�
0 � � �
start q3 q4 q7 q5 1 q6 q8
�
RYS. 4.13.b Konstruktor dla r1 =r3r4 (r= 01*).
Ostatecznie tworzymy konstrukcję dla wyra\enia r= r1 + r2 (r=01*+1) wykorzystując
konstruktor sumy teoriomnogościowej.
start q1 1 q2
� �
q9 q10
� �
0 � � � �
q3 q4 q7 q5 1 q6 q8
�
RYS. 4.14. NAS z � -ruchami dla wyra\enia regularnego 01*+1.
62
Rozdział 5 Gramatyki i języki formalne.
W tym rozdziale zostaną zdefiniowane takie pojęcia jak gramatyka, semantyka i
syntaktyka, a tak\e gramatyka bezkonstekstowa. Wyjaśniona zostanie klasyfikacja
Chomsky ego. Rozdział ten obejmuje równie\ informacje dotyczące notacji Backusa Naura,
która wykorzystywana jest do definiowania gramatyk bezkontekstowych wraz z przykładami.
5.1. Gramatyki podstawowe informacje.
Gramatyka to układ reguł, zbiór słów utworzonych z symboli języka. Słowa mogą być
interpretowane jako obiekty językowe ró\nego typu np.: jako formy wyrazowe, grupy
wyrazów i zdania. Gramatykę języka mo\na rozpatrywać jako zbiór powtarzających się reguł
budowy zdań nazywanych syntaktyczną strukturą języka.
Syntaktyka czyli składnia języka to reguły budowy zdań języka lub budowy
konstrukcji językowych. Semantyka języka jest to interpretacja tych reguł, zasady stosowania
składni.
Gramatyki formalne zajmują się pojęciami abstrakcyjnymi powstałymi na drodze
uogólnień pojęcia formy wyrazowej, grupy wyrazów, zdania. O ile zwykłe gramatyki
umo\liwiają określenie zbioru reguł budowy zdań, o tyle gramatyki formalne stanowią
pewien sposób badania i opisu zbioru reguł [AAFI 77] [HOPC 94]. Wyró\nia się trzy typy
gramatyk formalnych:
rozpoznająca jest gramatyką, która dla dowolnego słowa potrafi rozstrzygnąć, czy [ Pobierz całość w formacie PDF ]

Odnośniki