DFA تصغير خوارزمية Brzozowski

Question

أحاول تطبيق خوارزمية Brzozowski لتقليلها إلى أدنى حد من متابعتي هي الخوارزمية لنفسه.

DFA = d(r(d(r(NFA)))) 

أين r() هو عكس NFA و D() يحول NFA إلى DFA.

لكني لا أفهم ما هو معنى r() البحث في جوجل أيضا لا يعطي الكثير من المعلومات.

يمكن لأي شخص يرجى شرح ما هو r() من نفا.

أي خوارزمية بسيطة أخرى أو تطبيق C++ متاح، يرجى إعلامي بالرابط.

Answer 1

في الكود الخاص بـverse.c (تم العثور عليه هنا, ، ولكن الآن البائد) ستجد تعليقا /* Create reversed edges */.لذلك أود أن أقول ذلك r() هو عكس اتجاه جميع الحواف (بالإضافة إلى التأكد من أن الجهاز الآلي المعكوس لديه حالة بداية محددة جيدًا).

Answer 2

هذا هو التنفيذ من OpenFst.

في هذا الورق عبارة عن رسم تخطيطي (صفحة 15) يوضح نتائج تطبيق العملية العكسية.

الطريقة الأسهل للمساعدة في فهم عمليات FSM هي استخدام مكتبة مثل OpenFst لإنشاء الأجهزة ومعالجتها ثم تصور النتائج باستخدام Graphviz.