需要对这个冗长的DFA单词问题进行更好的解释(CS:形式语言和自动机课程)

问题描述 投票:0回答:1

我多次阅读此问题,但仍然不太了解。我只需要一些帮助来了解这里的情况。

<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLnN0YWNrLmltZ3VyLmNvbS9CcDBPQi5wbmcifQ==” alt =“整个问题的屏幕截图。”>

因此,我了解“物种”有三种类型:A,B和C。这些物种字母Σ吗?另外,在问题中列出的第一个DFA中,110状态:这些数字确切代表什么?我知道他们是

xyz,其中x,y和z分别是一个品种的数量

但是我不明白110在第一种状态下的含义。这是否意味着A和B有两个自己的孩子,或者A和B交配了?

来自此问题的问题是:

(a)DFA中与此奇怪的字符有关的字母Σ是什么 行星?另外,请说明指定语言中的字符串是什么 通过这些自动机。

(b)描述指定字符串是否属于的规则 语言。

(c)可以修改任何DFA,以便我们最多具有一个陷阱状态(通过 轻松修改原始DFA,以便任何导致 陷阱状态会导致单个特定的陷阱状态)。写 上面的自动机的转换矩阵。

(d)如果我们最初知道绘制所有其他DFA, 这个星球上确实有两个人(一个可能 上面的问题描述中提供了自动机。画另一个 “两个”)

(e)如果最初刚好是三个,请绘制该星球的所有DFA 地球上的个人。如果其中一些看起来像每个 除了“初始”状态外,您只需绘制一次即可 而不指定哪个状态是初始状态。

(f)我们定义三种状态,如下所示:必须失败状态: 那些肯定会导致地球崩溃的州。 ii。 可能失败的状态:可能导致行星故障的状态。 iii。 不能失败状态:永远不会导致失败的状态 行星。列出所有必须失败,可能失败和不能失败的状态 三个人。

(g)绘制初始状态为121的自动机。每种类型 这个自动机的状态是?

如果我能得到一些帮助来理解这个问题并帮助解决前两个问题,我将不胜感激!我正在尝试解决它,但我不太了解。谢谢!

automata computation-theory dfa formal-languages deterministic
1个回答
0
投票

但是我不明白110在第一种状态下的含义。这是否意味着A和B有两个自己的孩子,或者A和B交配了?

这表示该行星具有1 A,1 B和0C。由此产生的转变c表示1 A和1 B配对并死亡,产生2C。因此,这颗行星具有0 A,0 B和2 C,因此状态称为002

(a)DFA中与此奇怪的星球有关的字母Σ是什么?另外,请描述这些自动机指定的语言中的字符串是什么。

在图中,字母为{a, b, c}a代表B和C交配,b代表A和C交配,c代表B和C交配。

((b)描述指定字符串是否属于该语言的规则。

这很复杂。 DFA将取决于起始状态下每种物种的个体数量。基本上,转换是对三个变量A,B和C进行数学运算。每个转换都从两个变量中减去1,然后在第三个变量中加2-这意味着仅当至少两个变量非零时才可以进行转换。] >

考虑状态111。有三种可能的状态转换为三种可能的状态:a -> 300b -> 030c -> 003。我们考虑这些“失败”的行星,因为不会再繁殖,所以它们是接受状态。

考虑状态220。转换c使我们进入状态112a使我们到达301b让我们回到220。这是一个循环!因此,无限字符串是可能的。

注意,变量A,B和C的总和为常数。每个州的总和必须相同。因此,状态数最多将是使用三个非负整数项表示该总和的所有可能方式。

[继续探索上述属性,以了解有关过渡的更多信息。我会把它留给您作为练习。

© www.soinside.com 2019 - 2024. All rights reserved.