Конструктор конечных автоматов - Racket Language

Мне нужно создать конструктор конечной машины, который принимает все префиксы языка данной машины. Скажем, язык машины M1 L (M1) = "abba", тогда конструктор должен создать новую машину M2 такую, что L (M2) = {empty, a, ab, abb, abba}

Теперь в библиотеке есть конструктор под названием fsm, и его прототип выглядит так:

    (make-fsa list-of-states alphabet starting-state list-of-final-states list-of-rules)
;List-of-rules is the list of transitions such as (q0 a q1)
;the function returns a finite state machine

Я пытаюсь сделать каждое состояние конечным. Но так ли это работает?

Код ниже - это то, что у меня есть на данный момент:

#lang racket
(require fsm) ;provides the constructor and getters

(define M1
  (make-dfa ;constructor, provided by the fsm library
  '(q0 q1 q2) ;states
  '(a b) ;alphabet
  'q0 ; starting state
  '(q2) ;list of final states
  '((q0 a q1) ;list of rules
    (q0 b q0)
    (q1 a q0)
    (q1 b q2)
    (q2 a q2)
    (q2 b q2))))

; new constructor
(define M2 
  (make-dfa
  (sm-getstates M1) ;sm-getstates is a getter that gets a certain machine's states
  (sm-getalphabet M1) ;sm-getalphabet is a getter that gets a certain machine's alphabet
  (sm-getstart M1) ;sm-getstart is a getter that gets a certain machine's starting state
  (sm-getstates M1) ; TURNING EVERY STATE IN M1 A FINAL STATE, BUT DOES IT WORK?
  (sm-getrules M1))) ;sm-getrules is a getter that gets a certain machine's list of rules

state-machine dfa racket fsm nfa
person elChino    schedule 11.03.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Ваш план не работает. Рассмотрим эту машину:

Состояния: S, L, F Алфавит: a, b Начальное состояние: S Конечное состояние S

S-a-> L (стрелка от S к L дана a) S-b-> F L-a-> L

Строки, принимаемые этим компьютером: {b}

Если вы создадите новую машину, где L - конечное состояние, тогда {empty, a, aa, aaa, ...} будут приняты, но они не являются префиксами в исходной машине.

В вашей конструкции M2 только состояния M1, у которых есть путь к конечному состоянию, должны стать конечными состояниями в M2.

person soegaard    schedule 11.03.2015
comment
Mange tak. Мой план состоит в том, чтобы получить каждое состояние M1, что означает конечные состояния S, L и F. так что новая машина принимает {empty, a, aa, aaa, aaaaaaaa, .... b} и, следовательно, принимает все префиксы M1. - person elChino; 11.03.2015
comment
Det var så lidt. Если вы добавите только состояния, у которых есть путь к конечному состоянию, M2 будет распознавать префиксы строк, принимаемых только M1. Если вы превратите все состояния M1 в конечные состояния в M2, язык, принимаемый M2, будет слишком большим. - person soegaard; 11.03.2015
comment
Еще раз большое спасибо. Какой метод вы бы использовали для поиска пути к конечному состоянию? - person elChino; 11.03.2015
comment
Следующий алгоритм начинается с конечных состояний и движется назад ко всем состояниям, которые могут достичь конечного состояния: Создать очередь Q. Добавить все конечные состояния в очередь. Теперь переберите состояния в очереди, пока она не станет пустой. Для каждого состояния S в очереди Q: i) пометить состояние как конечное, ii) поместить все состояния, которые указывают на S, в очередь iii) пометить как s как обрабатываемые. В конечном итоге это отметит все состояния, у которых есть путь к конечному состоянию. В ii) помещать в очередь только ранее необработанные состояния. - person soegaard; 11.03.2015
comment
Спасибо, и я стал лучше понимать. Будет лучше, если у вас будет время показать мне на самом деле реализацию. В любом случае отмечаю это как ответ и хорошего дня! - person elChino; 11.03.2015
comment
Вы можете задать новый вопрос о том, как найти пути, и надеяться, что кто-нибудь ответит. Откуда библиотека fsm? - person soegaard; 11.03.2015