Finite-State-Maschinen, wie minimale und maximale Treffer zu implementieren

Question

Ich versuche, eine Fsm zu implementieren und es geht gut. Ich kann Zeichenfolgen eingeben und sehen, ob sie gültig sind und all diese Dinge.

Allerdings haben reguläre Ausdrücke (die fms sind) diese Eigenschaft, wo Sie angeben können, wie oft ein bestimmtes Zeichen auftreten kann, zB würde {2,4} "aa" und "aaa" akzeptieren, aber nicht "aaaaa" und "a"

Ich kann mir vorstellen, einen Zähler an Kanten, die zählen, wie oft sie getroffen wurden und dies verwenden, um irgendwelche Zeichen zu verweigern, nachdem der Zähler eine bestimmte Anzahl erreicht hat, aber Sie können nicht implementieren, weil es würde immer das erste Zeichen blockieren (außer Minimum ist 0).

Kennt jemand eine Möglichkeit, diese Funktion zu implementieren? es muss auch für wirklich große Zahlen wie ein {1.99999999999}

Answer 1

arbeiten Zu meinem Verständnis, diese Art von Einschränkung kann nicht dynamisch in einer endlichen Zustandsmaschine implementiert werden; Teile der FSM müssten statisch erweitert werden. In Ihrem Beispiel müssten für a{2,3} drei verschiedene separate FSMs erstellt werden, von denen einer aa akzeptiert, der zweite aaa akzeptiert und der dritte aaaa akzeptiert; diese müssten dann in der finalen FSM über einige leere Übergänge zu Alternativen gemacht werden. Der Grund dafür ist, dass die FSM selbst nicht den Pfad speichert, mit dem ihr aktueller Zustand erreicht wurde, so dass eine parametrisierte Form des Musters a{i,j} nicht überprüft werden kann.