مستخدم:Ohood aldosari/ملعب
بناء تومسون
بناء تومسون
عدلفي علوم الكمبيوتر ، فإن بناء تومسون هو عبارة عن نظام حلول حسابية خورازمية لتحويل التعبير من منتظمة إلى مكافئ غير محدود آلي متناهي لا ينتهي NFA . هذا NFA ممكن أن استخدامها لمطابقة السلاسل مقابل التغيير العادي . التعبيرات المنتظمة والآلية المحدودة وغير المحدودة هي تمثيل للغتان رسميتان .على سبيل المثال ، تستخدم أدوات معالجة النص تعبيرات منتظمة لوصف أنماط البحث ، ولكن NFAS هي الأكثر ملاءمة للتنفيذ على الكمبيوتر ومن ثم ، فهذه الخورازمية لها أهميه علمية منذ أن استطاعت جمع التعبيرات المنتظمة الى NFAS . من الناحية النظرية . هذه الخورازمية هي جزء من إثبات كلاهما يصل نفس اللغات اي اللغات المنتظمة ليمكن NFA جعلها حتمية باستخدام بناء الصلاحيات وتعليلها ، للحصول على أفضل استخدام الى ان يتواقف مع التعبيرات المنتظمة ومع ذلك NFA يمكن تفسيرها بشكل مباشر . ડડ
لتقرير اذا كان هناك تعبيران منتظمان لوصف نفس اللغة يمكن تحويل كلتاهما الى مكافئ غير محدود من خلال بناء تومسون إنشاءpowerset وتقليل DFA الى أدنى حد ، وكانت النتيجة موافقة الألية على إعادة استخدام الحالات , فإن لغات التعبيرات العادية متفق عليها .
الخورازمية :
عدلتعمل الخورازمية بشكل متكرر من خلال تقسيم التعبير الى NFA المكون لها من خلال مجموعه من القواعد . [1]
من تعبير عادي E وعنصر آلى A مع وظائف النقل .
- باحترام ડ الخصائص الاتية :
١- A له حالة أولية q0 والتي لا يمكن ان تندرج تحت حالات اخرى بمعنى اي حالة q واي حرف ( a,ડ( a,q لا تحتوي على q0 .
٢- A تحتوي على حالة واحدة لها في qf والتي تتسلسل مع اي حالة اخرى ، ذلك لأي حرف
( a,ડ( qf,a ، حيث = ø .
٣- يسمح ل C هو رقم رقم التسلسل لتعبير المنتظم E ويسمح ل s رقم التمثيل لجزء المشاركة وهذا a ,*,| و ε .
ثم رقم الحالة A يكون s-c2 ( خط حجم E )
٤ - يبلغ عدد التغيرات التي تغادر اي حالة اكثر من اثنين .
٥- منذ ان كانت NFA من حالة m في اكثر من e انتقال من اي حالة يمكن ان تصل طوليا n في الوقت (O(emn
تومسون NFA يمكن ان يطابق النمط في الزمن الخطي , المثبت في حجم الحروف الابجدية .[2]
القواعد :
عدلالقواعد التالية مصوره طبقاً [3] ( ١٩٨٦)Aho et al صفحه رقم ١٢٢ من المتبع (N(s و NE هما NFA للتعبير الجزئي t و s على التوالي .
التعبير الفارغ ε تحول الى
نموذج الحروف الابجدية تحول الى :
التعبير الفريد s| t تحول الى :
- الحالة q تذهب عبر ε و اما الى الحالة الابتدائية (N(t او (N(d الحالة النهائية تصبح محددة كل NFA وتدمج بواسطة اثنين من اننقال الى الحالة النهائية NFA
- بناء التعبير S|t يتحول الى :
الحالة الابتدائية ل (N(s
هي حالة ابتدائية ل كل NFA والحالة النهائية (N(t هي حالة نهائية ل كل NFA .
تعبير ( s* ( kleene star تحول الى :
انتقال ε يصل بين الحالة الابتدائية والحالة النهائية ل NFA مع الفرعية -(NFA N(s
هناك معامل انتقال ε من النهائي الداخلي الى المبدئي الداخلي لحالة (s) N يسمح بتكرار التعبير S طبقا ل عملية ( * ) .
التعبير المشترك (s) تحول الى (N(s بنفسه .
المثال :
عدل
هذه الصورة تعرف النتيجة لبناء تومسون في (ε|a*b) الشكل البيضاوي الوردي يتوافق مع a
الحذف البيضاوي يتوافق مع * a , الشكل البيضاوي الاخضر يتوافق مع b , والشكل البيضاوي البرتقالي يتوافق مع a*b والبيضاوي الازرق يتوافق مع ε.
العلاقة بين الخوارزميات الاخرى :
عدليعد بناء تومسون واحداً من العديد من خوارزميات بناء NFAS للتعبيرات المنتظمة [4], أولا الخوارزميات اعطت بواسطة , [5] (McNaughton and Yamada) .
التحول في نظرية تومسون لبناء خورازميات ( kleene's ) ترجمت التعبيرات الآلية الى تعبير منتظم .
خورازمية (Glushkov's ) للبناء مشابهة لنظرية تومسون للبناء بمجرد ازالة واحدة من انتقالات ε .
المراجع :
عدل- ^ 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" (PDF3
- ^ [1] 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.