计划中的有限状态机

Question

我正试图在Scheme中完成一个有限状态机。问题是，我不知道如何告诉它应该测试哪些字符。如果我想测试一个字符串“abc112”，那我该怎么做？

下面是代码：

#lang racket  
(define (chartest ch) 
    (lambda (x) (char=? x ch))) 
;; A transition is (list state char!boolean state) 
(define fsmtrlst 
    (list 
    (list 'start char-alphabetic? 'name) 
    (list 'start char-numeric? 'number) 
    (list 'start (chartest #\() 'lparen) 
    (list 'start (chartest #\)) 'rparen) 
    (list 'name char-alphabetic? 'name) 
    (list 'name char-numeric? 'name) 
    (list 'number char-numeric? 'number))) 

(define (find-next-state state ch trl) 
    (cond 
    [(empty? trl) false] 
    [(and (symbol=? state (first (first trl))) 
      ((second (first trl)) ch)) 
    (third (first trl))] 
    [else (find-next-state state ch (rest trl))])) 

(define fsmfinal '(name number lparen rparen)) 

(define (run-fsm start trl final input) 
    (cond 
    [(empty? input) 
    (cond 
     [(member start final) true] 
     [else false])] 
    [else 
    (local ((define next (find-next-state start (first input) trl))) 
     (cond 
     [(boolean? next) false] 
     [else (run-fsm next trl final (rest input))]))])) 

这里是我想测试的启动代码：

(fsmtrlst (list 'start (lambda (abc112) (char=? abc112)))) 

编辑：

OK ..整体产品okey，但是我的导师不满意它，..他希望我创建一个带有转换函数的有限状态机 - >类似于全局定义，它会说：当状态X中字符Y转到Z时那么我会测试一个字符列表，看看它是错误还是真实的......所以唯一的区别是代码不应该只使用数字和字母，而是使用任何字符...是不是有可能？谢谢您的回答

编辑2：现在我有基本的信息应该如何看起来像：

也就是说，整机看起来像

一个---------> B ----------> C ----------> D ---------->（E） 字母数字编号字母

(define fsmtrlst 
(list 
    (list 'A char-alphabetic? 'B) 
    (list 'B char-numeric? 'C) 
    (list 'C char-numeric? 'D) 
    (list 'D char-alphabetic 'E))) 

(define fsmfinal '(E)) 

(define fsmstart 'A) 

但我不知道如何编写fsmstart的定义。

谢谢你的回答。

它接受正好是字母，数字，数字，字母和其他的字符序列。编辑3：我在线上使用教程和我的导师老师提供的一本书。我想出了我想制作的fsm。感谢您的帮助。

只是出于好奇：

如何将不同有相当具体的FSM？

实施例：

START ---- “B” ----->状态A ----- “一个” ---->状态B ----- “C” - ----> FINAL STATE

只有当字符列表是“bac”而没有其他字符时，fsm才会成立。 这可能吗？

感谢您的反馈。

编辑4：

好吧，我能够做到写，但再一次，我不知道如何使文字的输入。这是代码：

有3个状态，但是从状态A到状态时只有C.

(define (chartest ch) 
    (lambda (x) (char=? x ch))) 

    (define fsm-trans 
     '((A, "a", B), (A, "b", A), (B, "c", C))) 

    (define (find-next-state state ch trl) 
     (cond 
     [(empty? trl) false] 
     [(and (symbol=? state (first (first trl))) 
       ((second (first trl)) ch)) <- And also this line returns an error 
     (third (first trl))] 
     [else (find-next-state state ch (rest trl))])) 


    (define fsm-final '(C)) 

    (define start-state 'A) 

    (define (run-fsm start trl final input) 
     (cond 
     [(empty? input) 
     (cond 
      [(member start final) true] 
      [else false])] 
     [else 
     (local ((define next (find-next-state start (first input) trl))) 
      (cond 
      [(boolean? next) false] 
      [else (run-fsm next trl final (rest input))]))])) 


    (run-fsm start-state fsm-trans fsm-final (list '("a", "c"))) <- I know this is the last problem with the code, the definition of the input. How can I tell Scheme what characters I want to test? 

谢谢你的回答会是真的！

Answer 1

我很好奇：我认为你没有写这个fsm？这是做家庭作业还是你想教自己？ FSM的代码看起来很好（实际上很好）。然而，你的启动行：

(fsmtrlst (list 'start (lambda (abc112) (char=? abc112)))) 

是没有意义的。这是为什么：fsmtrlst是有限状态机转换列表。它是在第一大代码块中定义的。它是而不是一个被调用的函数。我相信你想要调用的功能是run-fsm。这需要一个开始符号，一个转换列表，一个最终状态列表和一个输入。输入实际上不是一个字符串，而是一个列表。因此，你可以用下面的行启动它：

(run-fsm 'start fsmtrlst fsmfinal (string->list "abc112")) 

，将调用run-fsm与定义的过渡列表fsmtrlst，所定义的最终状态的列表，字符串“abc112”的输入就绪形式。

顺便提一下，除'start之外的所有内容都被定义为最终（接受）状态。不过，并非所有投入都接受投入。例如，取代“abc122”，“ABC（122”是不接受

这是你想要的

更新：？

您的修改，澄清事情你的fsmstart定义你确实错过了char-alphabetic?用法中的一个问号（？）fsmtrlst。难道你不知道如何使用你的新定义吗？首先，你应该删除旧的定义fsmtrlst和fsmfinal。 ，你可能会得到一个重复的定义错误。从你的新defi定义，你行执行应该是这样的：

(run-fsm fsmstart fsmtrlst fsmfinal (string->list "w00t")) 

这将返回#T，因为“w00t”是一个字符，后跟两个数字，后跟一个字符。

我推测你仍然有计划的语法规则的困难，而不仅仅是你的特定程序的逻辑问题。你可能想尝试一个更简单的练习。

更新2：你不应该考虑制定一个新的问题吗？

您最近的更新已打破该守则。 FSM的过渡部分的工作，因为过渡被定义为一个列表：

(from-state test-function to-state) 

您试图创建一个过渡：

(from-state string-literal to-state) 

你可以改变(A, "a", B)到(A (lambda (x) (string=? x "a") B)。

当您尝试调用函数时，您使用了一个函数，该函数需要一个字符列表并为其提供了一个字符串列表。这些不是一回事。另外，您是否注意到您在列表中添加了逗号，但是它们在代码中没有其他地方存在？这些错误是为什么我建议你开始计划教程。这些是基本的计划问题，与您的特定练习无关。我建议你将编辑回放到你昨天所做的。

很抱歉，我们不能再更新此答案。我想更新我的答案，以便如果有人带着类似的问题提出你的问题，他们会看到一个完整的答案。但是，您提供了一个移动目标。请考虑停止编辑并在有问题时提交新问题。