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

Question

Мне нужно построить конечный машинный конструктор, который принимает все префиксы заданного машинного языка. Скажем, язык машины 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 

Answer 1

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

Штаты: S, L, F алфавита: а, б начальное состояние: S Конечное состояние S

удовлетворяющем> L (стрелка от S до L дан) Sb- > F La-> L

Строки, принятые на этой машине: {б}

Если вы сделаете новую машину, где L представляет собой конечное состояние, то {пусто, а, аа, ааа, .. .} будут приняты, но они не являются префиксами в оригинальной машине.

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