时间戳

首页 > 解决方案 > 如何绘制语言 A={w | 的 DFA w 的每个偶数位置都有符号 0}？

computation-theory - 如何绘制语言 A={w | 的 DFA w 的每个偶数位置都有符号 0}？

问题描述

我需要为机器绘制 DFA。机器接受语言 A。

语言 A={w | w 的每个偶数位置都有符号 0} 和 Σ = {0,1}。

我画了 DFA。不确定它是否正确。

这是我的 DFA， DFA [图片]

我想知道它是否正确。如果它是错误的，那么如何纠正它。

标签： computation-theorydfanfaautomata-theory

解决方案

为了使这项工作，我们需要知道我们将获得哪个符号 - 偶数位置符号或奇数位置符号 - 如果我们即将获得偶数位置符号，则只接受零。我们可以识别我们将要获得具有两种状态的偶数位置符号还是奇数位置符号：qOdd 和 qEven。我们还需要一种方法让 DFA 识别它已经发现违反了阻止它以后接受字符串的约束；我们可以称那个状态为 qDead。每个状态需要两次转换；死状态总是转换到它们自己，并且 qOdd/qEven 将相互转换，直到看到 qEven 中的 1 违反了条件。

我们的 DFA 如下所示：

        /-----0----\          /-0,1-\
        |          |          |     |
        V          |          |     |
----->qOdd-0,1->qEven--1-->qDead<---/

推荐阅读