تجربة بناء طومسون
التعريف
في علم الحاسوب ، بناء طومسون هو خوارزمية لتحويل التعبير المنتظم إلي أتومات (مشغلات آلية) محدودة غير حتمية متكافئة. هذه الأتومات المحدودة غير الحتمية يمكن أن تستخدم لمطابقة السلاسل ضد التعبير المنتظم . التعبيرات المنتظمة والأتومات المحدودة غير الحتمية هما عرضان للغات الرسمية. على سبيل المثال ، تستخدم مرافق معالجة النص تعبيرات منتظمة لوصف أنماط البحث المتقدم لكن الأتومات المحدودة غير الحتمية هي أفضل ملائمة للتنفيذ علي الحاسوب. ولذا هذه الخوارزمية ذات أهمية عملية لأنها يمكن أن تجمع تعبيرات منتظمة في الأتومات المحدودة غير الحتمية. ومن الناحية النظرية هذه الخوارزمية هي جزء من إثبات أن كليهما يقبلان نفس اللغات بالضبط أي اللغات المنتظمة. ويمكن أن يصبح الأتوم المحدد غير الحتمي حتميا ببناء مجموعة أساسية ثم تقلل للحصول علي الحد الأمثل للأوتومات طبقا للتعبير المنتظم المعطي. ومع ذلك يمكن أيضا للأتومات المحددة غير الحتمية أن تفسر مباشرة. لوصف ما إذا كان يصف تعبيران منتظمان معطيان نفس اللغة ، يمكن أن يحول كل منهما إلي ما يعادل الحد الادنى للأوتومات المحدودة الحتمية عن طريق بناء طومسون و بناء مجموعة أساسية وتقليل الأتومات المحدودة الحتمية. لو فقط وافقت الأتومات الناتجة علي إعادة تسمية الحالات ستوافق لغات التعبيرات المنتظمة.
المحتوى
الخوارزمية
تعمل هذه الخوارزمية بشكل تكراري عن طريق تقسيم التعبير إلي تعبيراته الفرعية الجوهرية والتي من خلالها ستبني الأتومات المحدودة غير الحتمية باستخدام مجموعة من القواعد أكثر دقة ، من التعبير المنتظم E الأوتوماتون الناتج A مع الوظيفة الانتقالية ẟ تطبق الخصائص الآتية[1] :
- A لها حالة أولية واحدة بالضبط q0 والتي لا يمكن الوصول أليها من أي حالة أخرى. هذا لأي حالة q وأي حرف a
(ẟ (q,a لا تحتوي على q0 .
- A لها حالة نهائية واحدة بالضبط qf والتي لا يمكن الوصول إليها من أي حالة, وهذا لأي رسالة a
(Ø =ẟ (qf,a.
- لتكن c عدد تسلسل التعبير المنتظم E ولتكن s عدد الرموز بعيدا عن الأقواس هذا |, *, a و ε . بعد ذلك عدد حالات A هي 2s -c (خطي في حجم E )
- عدد الانتقالات المغادرة لأي حالة هي على الأكثر اثنان
- لأن الأتومات المحدودة غير الحتمية لحالات m وعلي الأكثر انتقالات e من أي حالة يمكن أن تطابق سلسة الطول n في وقت (O (emn ,أتومات طومسون المحدودة غير الحتمية يمكن أن تفعل نمط يتطابق في وقت خطي بفرض ثبوت حجم حرف الهجاء.[2]
القواعد
تصور القواعد الآتية حسب ماهو وآخرين فيما تتبع s)N) وt)N) هما الأتومات المحدودة غير الحتمية للتعبيرات الفرعية sو t علي التوالي [3]
يحول التعبير الفارغ إلى ε
يحول رمز a من الحرف الهجائي الداخل
يحول التعبير المتحد إلى s|t تذهب حالة q عن طريق ε إما إلي الحالة الأولية لـ s)N) أو t)N)
تصبح حالاتهم النهائية حالات متوسطة من كل الأتومات المحدودة غير الحتمية وتظهر عن طريق انتقالين ε اثنين إلي الحالة النهائية للأتومات المحدودة غير الحتمية .يحول التعبير المسلسل st إلى الحالة الأولية لـ هي الحالة الأولية لكل الأتومات المحدودة غير الحتمية . الحالة النهائية لـ s)N) تصبح الحالة الأولية لـ t)N). الحالة النهائية لـ t)N)هي الحالة النهائية لكل الأتومات المحدودة غير الحتمية.
يحول تعبير نجمة كلين إلى s*
يوصل انتقال ε الحالة الأولية والنهائية للأتومات المحدودة غير الحتمية مع الأتومات المحدودة غير الحتمية الفرعية في s)N) ما بينهم.
يسمح انتقال ε آخر من الحالة النهائية الداخلية للحالة الأولية الداخلية لـs)N) تكرار التعبير s طبقا لمشغل النجمة.
الأمثلة
مثالان معطيان الآن واحد غير رسمي صغير مع النتيجة وآخر أكبر مع تطبيق الخوارزمية خطوة بخطوة.
المثال الصغير
تظهر الصورة في الأسف نتيجة بناء طومسون علي (ε|a*b) . البيضاوي البمبي يناظر a ويناظر البيضاوي البترولي a* ويناظر البيضاوي الأخضر b ويناظر البيضاوي البرتقالي a*b ويناظر البيضاوي الأزرق ε
تطبيق الخوارزمية
كمثال تظهر الصورة نتيجة خوارزمية بناء طومسون علي التعبير المنتظم (0|(1(01*(00)*0)*1)*)* التي تشير إلي مجموعة أرقام ثنائية التي هي مضاعفات 3 . { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }.
يظهر الجزء الأيمن العلوي البناء المنطقي ( شجرة السياق ) للتعبير مع توضيح التسلسل ( بفرض وجود وضوح متباين ) التعبيرات الفرعية تسمي a-q لأغراض مرجعية. يظهر الجزء الأيسر الأتوماتون المحدود الغير حتمي الناتج من خوارزمية طومسون مع حالة إدخال وإخراج لكل تعبير فرعي ملون بالأرجواني والسماوي علي الترتيب. أغفل وضوح ε كملصق انتقالي - الانتقالات غير الملصقة هي في الحقيقة انتقالات ε . حالة الإدخال والإخراج حسب التعبير الجذري q هي حالة لبداية وقبول الأتومات علي الترتيب.
خطوات الخوارزمية كالآتي :
q : بداية تحويل تعبير نجمة كلين (0|(1(01*(00)*0)*1)*)*
b: بداية تحويل التعبير المتحد 0|(1(01*(00)*0)*1)*
a : حول الرمز 0
p : ابدأ تحويل تعبير نجمة كلين (1(01*(00)*0)*1)*
d : ابدأ تحويل التعبير المتسلسل 1(01*(00)*0)*1
c: حول الرمز 1
n: ابدأ تحويل تعبير نجمة كلين (01*(00)*0)*
f: ابدأ تحويل التعبير المتسلسل 01*(00)*0
e : حول الرمز 0
h : ابدأ تحويل تعبير نجمة كلين 1*
g : حول الرمز 1
h : أنهي تحويل تعبير نجمة كلين 1*
I : ابدأ تحويل تعبير نجمة كلين (00)*
j : ابدأ تحويل التعبير المتسلسل 00
i : حول الرمز 0
k : حول الرمز 0
j : أنهي تحويل التعبير المتسلسل 00
l : أنهي تحويل تعبير نجمة كلين (00)*
m : حول الرمز 0
f : أنهي تحويل التعبير المتسلسل 01*(00)*0
n : أنهي تحويل تعبير نجمة كلين (01*(00)*0)*
o : حول الرمز 1
d : أنهي تحويل التعبير المتسلسل 1(01*(00)*0)*1
p : أنهي تحويل تعبير نجمة كلين (1(01*(00)*0)*1)*
b : أنهي تحويل التعبير المتحد 0|(1(01*(00)*0)*1)*
q : أنهي تحويل التعبير المتحد
(0|(1(01*(00)*0)*1)*)*
يوضح في الأسفل ما يعادل الحد الأدنى للأتومات الحتمية
العلاقة بالخوارزميات الأخرى
خوارزمية طومسون واحدة من الخوارزميات العديدة لبناء الأتومات المحدودة غير الحتمية من تعبيرات منتظمة.[4] أعطيت خوارزمية باكرة بواسطة مكنوغتون و يمادا. وعلي عكس بناء طومسون ، تحول خوارزمية كلين الأتوماتون المحدود إلي تعبير منتظم. خوارزمية بناء جلوشكوف مشابهة لبناء طومسون عندما يحذف الانتقال ε .[5]
مراجع
- Ken Thompson (Jun 1968). "Programming Techniques: Regular expression search algorithm". Communications of the ACM. 11 (6): 419–422. doi:10.1145/363347.363387.
- Xing, Guangming. "Minimized Thompson NFA" (PDF).
- Alfred V. Aho, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques and Tools. Addison Wesley, 1986
- Watson, Bruce W. (1995). A taxonomy of finite automata construction algorithms (PDF) (Technical report). Eindhoven University of Technology. Computing Science Report 93/43.
- R. McNaughton, H. Yamada (Mar 1960). "Regular Expressions and State Graphs for Automata". IEEE Transactions on Electronic Computers. 9 (1): 39–47. doi:10.1109/TEC.1960.5221603.