Regex لكلمة سلسلة من 'a's و'b's.يظهر a بالضبط n*2 مرات في الكلمة و"b" بالضبط n*3 مرات

Question

أحتاج إلى إنشاء NFA (أو DFA، لا أعرف ما الذي سيكون عليه بعد) لهذه اللغة:

L(A) = { w ∈ {a,b}* | count(w, a) = 2i, count(w, b) = 3j, i, j ∈ ℕ }

يحدد العد (w, z) عدد مرات ظهور الحرف z في الكلمة w.في هذه الحالة يكون مضاعف 2 لـ "a"، ومضاعف 3 لـ "b".

أمثلة على كلمة صالحة:باب، ابب، باب، بابببا

لقد واجهت صعوبة في إنشاء جهاز آلي لذلك، لذا اعتقدت أنني سأحاول إنشاء تعبير عادي له أولاً لتحويله إلى NFA باستخدام هذه الطريقة, ، لأنه يمكنني اختباره بسهولة على مواقع اختبار regex.لكن هذا أيضًا لم ينجح.انتهى بي الأمر بعدد كبير جدًا من المجموعات التي يبدو أنها لا نهاية لها.

لا أعرف كيفية إنشاء تعبير عادي لذلك دون استخدام نوع من آلية العد.هل يمكن لأحد أن يعطيني تلميحا؟

Answer 1

يمكنك طراز Automaton الخاص بك كست ست حالات مختلفة، كل واحد يصف حالة (عدد (W، A) MOD 2، عدد (W، B) MOD 3).هناك ست دول محتملة مختلفة:

(0، 0) (0، 1) (0، 2) (1، 0) (1، 1) (1، 2)

في كل مرة تقوم فيها بقراءة "A"، تذهب من الحالة الحالية (E.G. (0، 1)) إلى الحالة المقابلة (-> (1، 1)).إذا قرأت آخر "A"، فأنت تعود إلى نفس الحالة مرة أخرى (-> (0، 1)).الشيء نفسه مع "B"، ولكن تغيير قيمة B (E.G. (0، 1) -> (0، 2) -> (0، 0) -> (0، 1)).

الدولة القابلية المسموح بها الوحيدة هي (0، 0).

باستخدام التدوين البصري:

href="http://cdn.imghack.se/cdn.imghack.se/images/ccea2c62451d81e477f73ac6fabc5134.png" er="nofollow noreferrer"> http://cdn.imghack.se/images/ccea2c62451d81e477f73ac6fabc5134.png

Answer 2

دعونا نرى، تحتاج إلى عدد حتى من A، وهذا يمنحك دولتين

giveacodicetagpre.

وتحتاج إلى عدة ثلاثة ل B:

giveacodicetagpre.

الجمع بين هذه الدول، يمكننا بناء القواعد التالية:

giveacodicetagpre.

لذلك، هذا قواعد منتظمة، جميع القواعد لها العودية اليمنى مع محطة واحدة Simbol وبأكثر ما غير متطوع، نأمل أن يساعد القواعد.

Answer 3

إن أبسط طريقة للتحقق من صحة مدخلاتك هي استخدام regex لمتطلباتك:

^(?=((b*a){2})*b*$)(?=((a*b){3})*a*$)[ab]*$

يستخدم هذا النظرة المستقبلية للتأكد من أن كمية "a" هي مضاعف للرقم 2 (بما في ذلك الصفر)، وبالمثل بالنسبة لـ "b" إحضار مضاعف إذا كان 3.

انظر أ live demo هذا التعبير العادي يعمل مع الأمثلة الخاصة بك وبعض الأمثلة غير الصالحة.