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