时间戳

首页 > 解决方案 > 计划中的 DFA（家庭作业）

scheme - 计划中的 DFA（家庭作业）

问题描述

处理一个要求在 Scheme 中编写 DFA 接受器的家庭作业问题。字母表：{0, 1} 开始状态：{Q0} 最终状态：{Q2}。字符串必须在序列中包含 01 才能被接受。状态：Q0 on 1 转换到 Q1。0 上的 Q0 过渡到 Q0。Q1 on 1 过渡到 Q2。Q1 在 0 上转换到 P。Q2 在 0 和 1 上转换到 Q1。老师要求每个状态都是一个函数，并返回一个它转换到的函数。(Q0 1) 返回 Q1 等。下面的代码尝试让事情运行，然后再担心检查 01 是否在字符串中。当前出现错误：“Q0：未绑定标识符；” 并且不知道为什么在做了一些搜索之后。任何指针都会有所帮助。问题是家庭作业，所以不要寻找直接答案。谢谢！

#lang racket
(define DFA-trans '((Q0 x) (Q1 x) '((Q2 x)) (P x)))

(define x '(1 1 0 1 0))

(define P(null? 1))

(define Q2 (lambda(x)
         (if (null? (car x))
             #t
         (if (equal? (car x) 0)
             (Q2 (cdr x))
         (if (equal? (car x) 1)
             (Q2 (cdr x))
             #t
             )))))

(define Q1 (lambda(x)
         (if (null? (car x))
             #f
         (if (equal? (car x) 0)
             (P (cdr x))
         (if (equal? (car x) 1)
             (Q2 (cdr x))
             #f
             )))))

(define Q0 (lambda(x)
         (if (null? (car x))
             #f
         (if (equal? (car x) 0)
             (Q0 (cdr x))
         (if (equal? (car x) 1)
             (Q1 (cdr x))
             #f
             )))))

(define DFA(map eval DFA-trans))
(DFA)

标签： schemeracketdfa

解决方案

不要为此使用 EVAL。

P、Q0、Q1、Q2 的定义看起来不错。

如果我们可以直接定义DFA，你可以直接删除DFA-trans。

假设 Q0 是开始状态，我想你可以简单地做到这一点

(define DFA (lambda () (Q0 x)))

并考虑使用 COND 而不是嵌套的 IF。

推荐阅读