بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
تبديل عبارات با قاعده به DFA
- مي توانيم يك عبارت با قاعده را بدون ايجاد NFA به DFA تبديل كنيم.
- در ابتدا به انتهاي عبارت باقاعده علامت # را اضافه مي كنيم داريم :
r è (r)#
- سپس درخت تجزيه و تركيب عبارت با قاعده مورد نظر را ترسيم مي نمائيم
- در درخت فوق تمامي نشانه هاي حروف الفبا، # و جاهاي خالي در محل برگ ها قرار مي گيرند.
- تمامي نودهاي داخلي در درخت مربوط به عملگرها خواهد بود.
- سپس تمامي برگ ها را شماره گذاري مي كنيم.
- به مثال در اسلايد بعد توجه نمائيد.
اسلاید 2 :
مثال : تبديل عبارت با قاعده به DFA
درخت ترسيم شده براي عبارت زير:
(a|b) * a #
- هر كدام از جايگاه ها شماره گذاري شده اند
- هر كدام از حروف ها در محل بر گ ها قرار دارند
- نودهاي داخلي محل قرارگيري عملگرها مي باشد
اسلاید 3 :
Followposتابع
در ادامه بايستي تابع Followpos را براي محل منتسب به برگ ها محاسبه مي كنيم
followpos(i) : مجموعه مكان هايي است كه بعد از مكان i قرار مي گيرند
لازم به ذكر است كه اين تابع فقط براي محل برگ ها تعريف مي شود و براي نودهاي داخلي قابل تعريف نيست.
.
براي مثال : ( a | b) * a #
1 2 3 4
followpos(1) = {1,2,3}
followpos(2) = {1,2,3}
followpos(3) = {4}
followpos(4) = {}
اسلاید 4 :
نحوه محاسبه توابع
firstpos, lastpos, nullable
براي محاسبه تابع followpos نيازمند محاسبه توابع زير در درخت
نحو مي باشيم :
firstpos(n) --
مجموعه اولين حروف توليد شده بوسيله زير عبارت درمحل n
- lastpos(n) --
- مجموعه آخرين حرف توليد شده بوسيله زير عبارت در محل n
- nullable(n) --
- اين تابع در صورتيكه محل خالي عضوي از رشته توليد شده بوسيله زير عبارت در محل n باشد برابر true و در غير اينصورت مساوي falseخواهد بود.
اسلاید 5 :
چگونه followposرا برآورد كنيم؟
براي محاسبه تابع followpos دو قانون زير را در نظر مي گيريم :
1 – اگر سطح n يك cat-node باشد و دو انشعاب c1(چپ) و c2 (راست) داشته باشد و i محلي در مجموعه lastpos(c1) باشد تمامي اعضاي
firstpos(c2) در تابع followpos(i) قرار خواهند گرفت.
2 – اگر سطح n يك star-node باشد وi محلي در مجموعه lastpos(n) باشد تمامي اعضاي firstpos(n) در تابع followpos(i) قرار خواهند گرفت.
اگر توابع firstpos و lastpos براي هر نود درخت محاسبه شوند تابع followpos با يك پيمايش عمقي در درخت نحوي قابل محاسبه خواهد بود.
اسلاید 6 :
مثال ( a | b) * a #
قرمزها– firstpos
آبي ها – lastpos
پس از محاسبه توابعfirstpos و lastpos
تابع followpos را به صورت زير محاسبه
مي كنيم.
followpos(1) = {1,2,3}
followpos(2) = {1,2,3}
followpos(3) = {4}
followpos(4) = {}
- پس از محاسبه followpos براي ايجاد DFA آماده مي شويم.
- .
اسلاید 7 :
الگوريتم تبديل (عبارت باقاعده به DFA)
- درخت نحو عبارت (r)# را ايجاد مي كنيم.
- توابع followpos, firstpos, lastpos, nullable را محاسبه مي كنيم .
- تابع firstpos(root) را بعنوان يك حالت علامت نخورده از حالات DFA در نظر مي گيريم.
- تا زماني كه حالت S از مجموعه حالت هاي DFA علامت نخورده است مراحل زير انجام مي پذيرد:
–حالت S را علامت مي زنيم.
–براي هر ورودي با علامت a
- در صورتيكه s1…….sn مكان هاي موجود در S بوده و ليبل آن مكان ها a باشد.
- S’çfollowpos(s1) È ... Èfollowpos(sn)
- move(S,a) ç S’
- اگر S’ خالي نبوده و جزو حالتهاي DFA نيز نباشد آن را جزو حالت هاي علامت نخورده DFA قرار مي دهيم.
- حالت شروع DFA firstpos(root) مي باشد.
- حالت پذيرش DFA تمامي حالت هايي است كه در آن مكان # وجود داشته باشد.
اسلاید 8 :
followpos(1)={1,2,3} followpos(2)={1,2,3} followpos(3)={4} followpos(4)={}
S1=firstpos(root)={1,2,3}
ß mark S1
a: followpos(1) Èfollowpos(3)={1,2,3,4}=S2 move(S1,a)=S2
b: followpos(2)={1,2,3}=S1 move(S1,b)=S1
ß mark S2
a: followpos(1) Èfollowpos(3)={1,2,3,4}=S2 move(S2,a)=S2
b: followpos(2)={1,2,3}=S1 move(S2,b)=S1
حالت شروعS1 حالت پذيرش {S2}
اسلاید 9 :
مثال -- ( a | e) b c* #
followpos(1)={2} followpos(2)={3,4} followpos(3)={3,4} followpos(4)={}
S1=firstpos(root)={1,2}
ß mark S1
a: followpos(1)={2}=S2 move(S1,a)=S2
b: followpos(2)={3,4}=S3 move(S1,b)=S3
ß mark S2
b: followpos(2)={3,4}=S3 move(S2,b)=S3
ß mark S3
c: followpos(3)={3,4}=S3 move(S3,c)=S3
S1شروع حالت {S3} حالت پذيرش
