Как реализовать FSM — конечный автомат на Java
У меня есть дела по работе, и мне нужна твоя помощь. Мы хотим реализовать FSM — Finite State Machine , чтобы идентифицировать последовательность символов (например: A, B, C, A, C) и сообщать, принята ли она. Мы думаем реализовать три класса: State , Event и Machine . Класс state представляет узел в FSM , мы думали реализовать его с помощью State design pattern , каждый узел будет выходить из состояния абстрактного класса, и каждый класс будет обрабатывать различные типы событий и указывать переходы в новое состояние. На ваш взгляд, это хорошая идея? Во-вторых, мы не знаем, как сохранить все переходы. Мы снова подумали о том, чтобы реализовать это с помощью какого-то типа map , который удерживает начальную точку и получает какой-то вектор со следующими состояниями, но я не уверен, что это хорошая идея. Я был бы рад получить некоторые идеи о том, как это реализовать, или, может быть, вы дадите мне несколько отправных точек. Как мне сохранить FSM, то есть как построить дерево в начале программы? Я погуглил и нашел много примеров, но ничего мне не помогло. Большое спасибо.
Хорошая идея, конечно, но если вы собираетесь идентифицировать строки, не лучше ли вам использовать, например, регулярное выражение? — person xtofl   schedule 04.11.2012
У меня есть библиотека, на которую вы, возможно, захотите посмотреть: github.com/mtimmerm/dfalex — person Matt Timmermans   schedule 07.08.2019
Ответы (7)
Сердцем конечного автомата является таблица переходов, которая переводит состояние и символ (то, что вы называете событием) в новое состояние. Это просто двухиндексный массив состояний. Для разумности и безопасности типов объявите состояния и символы как перечисления. Я всегда добавляю элемент «длины» каким-либо образом (в зависимости от языка) для проверки границ массива. Когда я вручную кодирую конечный автомат, я форматирую код в формате строки и столбца с использованием пробелов. Другими элементами конечного автомата являются начальное состояние и набор принимающих состояний. Самая прямая реализация набора принимающих состояний — это массив логических значений, проиндексированных состояниями. В Java, однако, перечисления являются классами, и вы можете указать аргумент «принятие» в объявлении для каждого перечисляемого значения и инициализировать его в конструкторе перечисления. Для типа машины вы можете написать его как универсальный класс. Он принимает два аргумента типа: один для состояний и один для символов, аргумент массива для таблицы переходов и одно состояние для начального. Единственная другая деталь (хотя и критическая) заключается в том, что вам нужно вызвать Enum.ordinal (), чтобы получить целое число, подходящее для индексации массива перехода, поскольку у вас нет синтаксиса для прямого объявления массива с индексом перечисления (хотя должно быть быть). Чтобы предотвратить одну проблему, EnumMap не будет работать для таблицы переходов, потому что требуемый ключ — это пара значений перечисления, а не одно.
enum State < Initial( false ), Final( true ), Error( false ); static public final Integer length = 1 + Error.ordinal(); final boolean accepting; State( boolean accepting ) < this.accepting = accepting; >> enum Symbol < A, B, C; static public final Integer length = 1 + C.ordinal(); >State transition[][] = < // A B C < State.Initial, State.Final, State.Error >, < State.Final, State.Initial, State.Error >>; Это действительно хорошая идея. Мне нужно, чтобы вы уточнить, пожалуйста. Что вы имеете в виду в двухиндексном массиве состояний, и если у меня есть пара маршрутов из одного состояния? Для класса состояния у нас есть абстрактный класс, которым является каждый производный класс (начальное состояние, обычное состояние и принятое состояние), таким образом, у нас есть тип для каждого из них. Как вы думаете, нам нужен машинный класс как общий класс? И последнее: есть ли у вас какая-нибудь ссылка на то, что представлен ваш метод? Спасибо большое за вашу помощь. — person Ofir A.; 05.11.2012
Двухиндексный массив — это двумерный массив. См. Пример. Состояния запуска и состояния принятия являются обычными состояниями. Для этого вам не нужны и даже не нужны отдельные классы. Принятие — это логический предикат состояний. Начальное состояние — это свойство конечного автомата, а не самого состояния. Сама машина не обязательно должна быть универсальной, хотя я считаю, что это хорошая практика. В частности, он позволяет вам проводить модульное тестирование кода конечного автомата независимо от конкретного конечного автомата, который вы хотите использовать с ним, который получит свой собственный набор тестов. — person eh9; 05.11.2012
Спасибо за вашу помощь. До сих пор я создавал абстрактный класс для состояния, производные классы относятся к разным типам (начало, стандарт, конец и ошибка). Каждое состояние имеет символ hashTable ‹, состояние›, которое содержит его дочерние элементы, или состояние ошибки в случае null. Сейчас я хочу напечатать другое сообщение для другой последовательности. Есть ли у вас предложения, как этого добиться? Спасибо. — person Ofir A.; 07.11.2012
Если вы хотите, чтобы сообщения были специфичными для последовательностей, вам нужно состояние, которое представляет эту последовательность. Когда вы входите в состояние, вы можете инициировать свое действие. Но эта проблема заключается в том, как спроектировать машину, а не реализовать, как это был ваш первоначальный вопрос. — person eh9; 07.11.2012
У меня к вам последний вопрос. Эта реализация взята из какого-то интервью. Они сказали мне, что у меня есть абстрактный класс для State, а производные классы должны реализовывать логику конечного автомата. Я думаю, что каждый производный класс должен быть из другого типа, как я уже сказал, например, start, standard, end и error. Как вы думаете, это правильный выбор, или вы можете придумать другую идею? Спасибо. — person Ofir A.; 07.11.2012
Я думаю, что помещать информацию о переходе между состояниями в разрозненную коллекцию конечных автоматов (обычно) действительно глупо. Это показывает мне, что людям, задающим вопрос, никогда не нужно было создавать серьезную и надежную государственную машину. В частности, просто бросать все остальное в какую-то корзину с неопределенным поведением аналитически лениво и обычно создает больше проблем в долгосрочной перспективе. — person eh9; 07.11.2012
Таким образом, вам не нужно объявлять static length в Java. Вместо этого используйте State.values().length или Symbol.values().length . — person Yahor; 15.06.2015
@Yahor Кеширование длины (некоторым образом) повышает эффективность, поскольку метод Enum.values () повторно создает массив значений каждый раз, когда он вызывается — person Nathan Adams; 03.11.2018
@NathanAdams Даже когда эффективность имеет значение, static public final int length = State.values().length чрезвычайно эффективен, поскольку вызывается только один раз. См. Также вопрос «длина значений перечисления по сравнению с частным полем» — person Yahor; 14.11.2018
Русские Блоги
Конечный автомат Java (шаблон проектирования состояния)
Конечный автомат Java (шаблон проектирования состояния)
При написании кода иногда встречаются более сложные swith. case. с if. else. Утверждение. В этот момент я иногда думаю о конечном автомате, использующем Конечный автомат заменить swith. case. с if. else. Можно:
- Снизить сложность программы;
- Повышение ремонтопригодности программы;
- Модель конечного автомата воплощает принцип открытия и закрытия, а также принцип единой ответственности.
Каждое состояние является подкатегорией, добавление состояния требует добавления подкатегории; изменение состояния требует изменения только одной категории.
Выше приведены преимущества конечных автоматов. Он также имеет Недостаток ：
- Увеличится использование подклассов конечного автомата, то есть расширение классов, которое требует от программистов самостоятельных измерений во время разработки.
Определение режима состояния:
Allow an object to alter its behavior when its internal state changes.The object will appear to change its class.
позволяет объекту изменять свое поведение при изменении его внутреннего состояния. Похоже, он изменил свой класс (это не очень хорошо переведено, здесь Он должен отражать его инкапсуляцию: внешние вызовы не должны знать, как изменяется его внутреннее состояние и поведение. )。
например
Лифт мы ходим каждый день, он имеет четыре состояния: Откройте, закройте, бегите, остановитесь.
| Col1 | Поведение при открытии двери | Закрытие поведения | Беговое поведение | Остановить поведение |
|---|---|---|---|---|
| Открытое состояние | no | yes | no | no |
| Закрытое состояние | yes | no | yes | yes |
| Состояние работы | no | no | no | yes |
| Состояние остановки | yes | no | yes | no |
LiftState.java
/** * Определите поведение лифта: открыть, закрыть, запустить, остановить */ public abstract class LiftState // Имеем объект лифта, используемый для обновления текущего состояния лифта protected Lift mLift; /** * Представьте созданный объект лифта через конструктор * * @param lift */ public LiftState(Lift lift) this.mLift = lift; > /** * Поведение: откройте дверь лифта */ public abstract void open(); /** * Поведение: закройте дверь лифта */ public abstract void close(); /** * Поведение: работа лифта */ public abstract void run(); /** * Поведение: лифт перестает работать */ public abstract void stop(); > Четыре состояния лифта
public class OpeningState extends LiftState public OpeningState(Lift lift) super(lift); > @Override public void open() // Выполняем действие открытия двери System.out.println(«Выполнить действие открытия двери»); > @Override public void close() // Выполнение действия закрытия двери // 1. Перевести в закрытое состояние mLift.setState(mLift.getCloseingState()); // 2, закрываем дверь mLift.close(); > @Override public void run() // do noting // Дверь открыта, текущее действие не может быть выполнено > @Override public void stop() // do noting // Когда дверь открыта, остановка не выполняется > > public class ClosingState extends LiftState public ClosingState(Lift lift) super(lift); > @Override public void open() // Выполняем действие открытия двери // 1. Перейти в открытое состояние this.mLift.setState(mLift.getOpenningState()); // 2. Открываем дверь this.mLift.open(); > @Override public void close() System.out.println(«Выполнить закрывающее действие»); > @Override public void run() // запускаем действие // 1. Статус выполнения this.mLift.setState(mLift.getRunningState()); // 2. Выполнить действие this.mLift.run(); > @Override public void stop() // остановить действие // 1. Преобразование в состояние остановки this.mLift.setState(mLift.getStoppingState()); // 2, стоп this.mLift.stop(); > > public class RunningState extends LiftState public RunningState(Lift lift) super(lift); > @Override public void open() // do noting > @Override public void close() // do noting > @Override public void run() // запускаем действие System.out.println(«Лифт ходит вверх-вниз . »); > @Override public void stop() // остановить действие // 1. Преобразование в состояние остановки this.mLift.setState(mLift.getStoppingState()); // 2, останавливаем действие this.mLift.stop(); > > public class StoppingState extends LiftState public StoppingState(Lift lift) super(lift); > @Override public void open() // Действие открытия двери // 1. Открытое состояние двери this.mLift.setState(mLift.getOpenningState()); // 2. Выполнить действие открытия двери this.mLift.open(); > @Override public void close() // do noting > @Override public void run() // запускаем действие // 1. Статус выполнения this.mLift.setState(mLift.getRunningState()); // 2. Выполнить действие this.mLift.run(); > @Override public void stop() // Лифт останавливается System.out.println(«Лифт перестал работать . »); > > Определить класс лифта
/** * Определить класс лифта */ public class Lift // Определяем все состояния лифта private LiftState openningState; private LiftState closingState; private LiftState runningState; private LiftState stoppingState; // Определяем текущий статус лифта private LiftState mCurState; /** * Метод строительства */ public Lift() openningState = new OpeningState(this); closingState = new ClosingState(this); runningState = new RunningState(this); stoppingState = new StoppingState(this); > /** * Выполните действие открытия двери */ public void open() mCurState.open(); > /** * Выполнить действие закрытия двери */ public void close() mCurState.close(); > /** * Выполнять беговые действия */ public void run() mCurState.run(); > /** * Выполните стоп-действие */ public void stop() mCurState.stop(); > // ################# Установить текущий статус лифта ################### /** * Установить текущий статус лифта * * @param state */ public void setState(LiftState state) this.mCurState = state; > // ################## Получить полный статус лифта ################### public LiftState getOpenningState() return openningState; > public LiftState getCloseingState() return closingState; > public LiftState getRunningState() return runningState; > public LiftState getStoppingState() return stoppingState; > > пробег
public static void main(String[] args) Lift lift = new Lift(); lift.setState(new ClosingState(lift)); lift.open(); lift.close(); lift.run(); lift.stop(); > результат операции
Выполнить действие открытия двери Выполнить действие закрытия двери Лифт ходит вверх и вниз... Лифт остановился...