Мне нужно построить конечный машинный конструктор, который принимает все префиксы заданного машинного языка. Скажем, язык машины 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
Mange tak. Мой план состоит в том, чтобы получить каждое состояние M1, что означает S, L и F конечные состояния. так что новая машина принимает {empty, a, aa, aaa, aaaaaaaa, .... b} и, следовательно, покрывает все префиксы M1. – elChino
Det var så lidt. Если вы добавите только состояния, которые имеют путь к окончательному состоянию, M2 будет распознавать префиксы строк, принимаемых только M1. Если вы перевернете все состояния M1 в конечные состояния в M2, язык, принятый M2, будет слишком большим. – soegaard
Еще раз спасибо. Какой метод вы бы использовали для поиска пути к окончательному состоянию? – elChino