Программа конечных автоматов

Question

Мне поручено создать небольшую программу, которая может считывать в определении FSM из ввода, читать строки из ввода и определять, принимаются ли эти строки FSM на основе определения. Мне нужно написать это в C, C++ или Java. Я прочел сеть за идеи о том, как начать, но лучшее, что я мог найти, это статья в Википедии по адресу Automata-based programming. Приведенный пример C, похоже, использует перечисленный список для определения состояний, это нормально, если состояния жестко закодированы заранее. Опять же, мне нужно иметь возможность действительно читать количество состояний и определение того, что должно делать каждое государство. Любые предложения приветствуются.

UPDATE: я могу сделать алфавит небольшой (например, {а} б) и принять другие конвенции, такие как состояние старт всегда состояние 0. Я позволил установить разумные ограничения на число состояний, например, Резюме не более 10.

Вопрос:

• Как реализовать FSA?

Answer 1

Сначала получите список всех состояний (N из них) и список всех символов (M из них). Затем есть 2 способа пойти, интерпретировать или генерировать код:

1. Интерпретация. Создайте матрицу NxM, где каждый элемент матрицы заполняется соответствующим номером состояния назначения или -1, если их нет. Затем просто введите начальную переменную состояния и начните обработку ввода. Если вы получите состояние -1, вы потерпите неудачу. Если у вас заканчиваются входные символы без перехода в состояние успеха, вы терпите неудачу. В противном случае вам это удастся.

2. Генерация кода. Распечатайте программу на C или вашем любимом языке компилятора. Он должен иметь переменную состояния целочисленного состояния, инициализированную начальным состоянием. Он должен иметь для петля над входными символами, содержащую переключатель на переменную состояния. У вас должен быть один случай для каждого состояния и в каждом случае иметь оператор switch для текущего символа, который изменяет переменную состояния.

Если вы хотите что-то даже быстрее, чем 2, и что это обязательно, чтобы вы провалили (!), Чтобы избавиться от переменной состояния и вместо того, чтобы использовать Гото :-) Если вы завалить, вы можете утешать самостоятельно осознавая, что это то, что делают компиляторы.

P.S. Вы можете получить, что ваш F изменен на A, если вы узнаете петли и т. Д. На диаграмме состояний и распечатаете соответствующие , а и , если, а не с использованием goto.

Answer 2

Если вы используете объектно-ориентированный язык, такой как Java или C++, я бы рекомендовал вам начать с объектов. Прежде чем вы будете беспокоиться о форматах файлов и т. П., Получите хорошую объектную модель для автоматов с конечным состоянием и как они ведут себя. Как вы будете представлять состояния, переходы, события и т. Д.? Будет ли ваш FSA составным? После того, как у вас будет такая работа, вы можете правильно получить форматы файлов. Все будет сделано: XML, текст и т. Д.

Answer 3

Один неструктурированный способ представления автомата является матрицей перехода, которая позволяет представлять для каждого текущего состояния и каждого входного символа то, что является следующим состоянием.

Answer 4

Вы на самом деле не задали вопрос. Вы получите дополнительную и лучшую помощь, если у вас есть конкретный question для конкретной задачи (но все же дайте общую цель). Вопрос должен быть узким по охвату (например, не «Как я могу реализовать FSA?»).

Что касается представления FSA (похоже, что у вас возникают трудности), читайте дальше.

Начните с рассмотрения определению FSM: это алфавит Σ, множество состояний S, начальное состояние s, набор принимает состояний и переход функции δ от состояния и символа к состоянию. Вы должны быть в состоянии определить эти свойства из ввода. Любые состояния, недоступные для функции перехода, можно отбросить для получения эквивалентного FSM. Таким образом, минимальная совокупность состояний и алфавита неявна в функции перехода; вы можете сделать ваш FSM более удобным в использовании (и сложнее реализовать, но не намного сложнее), не требуя ни Σ, либо S на входе.

Вам не нужно использовать то же представление для состояний, которые использует вход. Вы можете использовать целые числа без знака для вашего внутреннего представления, если у вас есть карта от целых чисел до строк и строк до целых чисел, чтобы вы могли преобразовать внутреннее представление и внешнее представление. Таким образом, ваша функция перехода может быть сохранена как массив, поэтому шаг перехода может выполняться в постоянное время.

Простым подходом было бы использовать внешнее представление как ваше внутреннее представление.С помощью этой опции функция перехода будет храниться в виде карты из строк и символов в строки. На этапе перехода, вероятно, будет O (log (| S | + | Σ |)), учитывая производительность большинства структур данных карты. Если символы представлены целыми числами (например, char с), функция перехода может быть представлена ​​в виде карты из строк в массив строк, что дает производительность O (log (| S |)).

Еще одна опция, смоделированная после графического представления FSM, заключается в создании класса для состояний. Состояние имеет имя (внешнее представление). Государства несут ответственность за переходы; отправить символ в состояние и вернуть другое состояние.

Хранить набор состояний в виде карты от имен к состояниям.

Здесь вы идете, три разных места для начала, каждый с другим видом представления состояний.

Answer 5

Остановите думать обо всем сразу. Сделайте одну вещь в то время

- come with language of state machine 
- come with language for stimulus 
- create sample file of one state machine in language 
- create sample file of stimulus 
- come with class for state 
- come with class for transition 
- come with class for state machine as set of states and transitions 
- add method to handle violation to state class 
- code a little parser for language 
- code another parser for language 
- initial state 
- some output thing like WriteLn here and there 
- main method 
- compile 
- run 
- debug 
- done 

Answer 6

Путем OpenFst инструментарий делает это: FSM имеет вектор состояний, каждое из которых имеет вектор дуг. Каждая дуга имеет метку ввода (и вывода), идентификатор целевого состояния и вес. Вы можете взглянуть на код. Возможно, это вдохновит вас.