التعبيرات العادية التكافؤ

Question

هل هناك طريقة لمعرفة ما إذا كانت التعبيرات العادية التعسفيتين تعادلان؟ يبدو وكأنه مشكلة معقدة بالنسبة لي، ولكن قد يكون هناك بعض آلية تبسيط DFA أو شيء من هذا؟

Answer 1

لاختبار التكافؤ يمكنك حساب الحد الأدنى من DFAS. بالنسبة للتعبيرات ومقارنتها.

Answer 2

تسري القدرة على المساواة هي واحدة من الخصائص الكلاسيكية للتعبيرات العادية. (NB هذا لا يحمل إذا كنت تتحدث حقا عن التعبيرات العادية بيرل أو بعضها من الناحية الفنية غير العادية Superlanguage.)

قم بتحويل الدقة إلى Automata Finited Automata A و B، ثم قم ببناء Automaton AB الجديد بحيث يكون قبول الدول التي تتحول إلى حالات البداية في ب، وأنها مقلولة ودول قبول ب. يمنحك هذا Automaton يقبل كل هذه الأوتار المقبولة من قبل، باستثناء جميع تلك المقبولة من قبل B.

افعل الشيء نفسه بالنسبة ل BA، وتقليل سواء إلى FAS النقي. إذا لم يكن لدى FA لا يقبل الدول التي يمكن الوصول إليها من حالة البداية، فإنها تقبل اللغة الفارغة. إذا تمكنت من إظهار أن كل من AB و BA فارغة، فقد أظهرت أن A = B.

Edit هيه، لا أستطيع أن أصدق أي شخص لاحظ خطأ العملاق هناك - واحدة متعمدة، بالطبع :-P

سوف تقبل شركة Automata AB كما هو موضح هذه السلاسل التي يتم قبولها النصف الأول من قبل ألف والنصف الثاني غير مقبول من قبل B. بناء مستهدف AB هي عملية صعبة قليلا. لا أستطيع التفكير في الأمر من أعلى رأسي، لكنني أعرف أنه محدد جيدا (ومن المحتمل أن ينطوي على خلق دول إلى تمثيل منتجات القبول في الدول غير القابلة للقبول في ب).

Answer 3

هذا يعتمد حقا على ما تقصد التعبيرات العادية. نظرا لأن الملصقات الأخرى أشارت، فإن تقليل التعبيرات إلى الحد الأدنى من DFA يجب أن تعمل، لكنها تعمل فقط على التعبيرات العادية النقية.

بعض البنيات المستخدمة في العالم الحقيقي Regex Libs (الخلفية على وجه الخصوص) تمنحهم القدرة على التعبير عن اللغات التي ليست منتظمة، لذلك لن تعمل خوارزمية DFA من أجلهم. على سبيل المثال Regex: ([a-z]*) \1 يطابق حدوث مزدوج لنفس الكلمة المفصولة عن طريق المسافة (a a و b b لكن لا b a ولا a b). لا يمكن التعرف على هذا بواسطة Automaton المحدود على الإطلاق.

Answer 4

ناقش هذين المواضيعان perlmonks هذا السؤال (على وجه التحديد، قراءة ردود Blokhead):

• الرضا النسبي عن Regexps
• اختبار المعادلة Regex.