finite-automata - 确定性/非确定性状态系统映射

Question

我在一本关于非确定性映射的书中读到，对于 M=(Q,∑,trans,q _{0 ,F)，存在从 Q*∑ 到 2} ^Q的映射，其中 Q 是一组状态。但我无法理解它是如何 2 ^Q；如果有 3 个状态a、b、c，它如何映射到 8 个状态？

Answer 1

我总是发现考虑这些的最简单方法（因为状态集是有限的）是让每个子集都是一个 base-2 数字的编码，范围从 0（所有位为零）到 2 ^|Q| -1（所有位为一），其中数字中的位与状态集 Q 中的成员一样多。然后，您可以只取其中一个数字，并通过使用特定位是否将其映射到子集在数量设置。简单的！

这是一个工作示例，其中 Q = { a , b , c }。在这种情况下，|Q| 是 3 （有三个元素），所以 2 ³是 8。这意味着如果我们说前导位是元素a，下一位是b，而尾随位是c：

• 0 = 000 = {}
• 1 = 001 = { c }
• 2 = 010 = { b }
• 3 = 011 = { b,c }
• 4 = 100 = {一个}
• 5 = 101 = { a,c }
• 6 = 110 = { a,b }
• 7 = 111 = { a,b,c }

看？最初的三个状态已转换为 8 个，并且我们有它们的自然编号，如果我们选择，我们可以使用它来创建这些状态的标签。

现在，在非确定性上下文中对此进行解释。基本上，非确定性意味着我们不确定自己处于什么状态。我们使用伪状态来表示这一点，伪状态是我们可能处于的“真实”状态的集合；如果我们有完全的非确定性，那么我们处于所有真实状态都可能的伪状态（即 { a,b,c }），而没有真实状态可能的伪状态（即 {} ) 是相反的（在过渡系统中确实应该是不可能达到的）。在实际系统中，您通常不会处理这些极端情况中的任何一个。

如何将确定性转换系统转换为非确定性系统的逻辑比我想在这里介绍的要复杂得多。（我必须阅读一篇实质性的博士论文才能学习它，所以它绝对比一个 SO 答案更有价值！）

Answer 2

2 ^Q表示 Q 的所有子集的集合。对于每个状态 q 和 sigma 中的每个字母 x，都有一个 Q 状态的子集，您可以从带有字母 x 的 q 进入。所以是的，如果有三个状态 abc，那么集合 2 ^Q由 8 个元素 {{}、{a}、{b}、{c}、{a,b}、{a,c}、{b,c} , {a,b,c}}。它不映射到 8 个状态，它映射到这 8 个集合之一。高温高压