有限状态机构造函数 - Racket Language

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 字母表：a,b 起始状态：S 最终状态 S

S-a->L（给定a从S到L的箭头） S-b->F L-a->L

本机接受的字符串：{b}

如果你制造一台 L 是最终状态的新机器，那么 {empty,a,aa,aaa,...} 将被接受，但它们不是前缀在原机中。

在您构建 M2 时，只有 M1 中有通往最终状态的路径的状态才能成为 M2 中的最终状态。

有限状态机构造函数 - Racket Language

Finite state machine constructor - Racket Language

state-machine

fsm

dfa

nfa

racket