模型检查：使用 NFA 的错误前缀
Model Checking : Bad Prefixes using NFA
我们使用 NFA 为安全性 BadPrefixes 建模 property.I 想了解给定的安全性 属性 如何对 NFA 建模。
以下图片供参考。
例如，为了安全 属性 P2，有人可以解释一下如何知道需要多少个状态（解决方案有 4 个）以及在边缘使用哪种逻辑，图 3 和图.4 ，选择边来满足 badprefixes P1 和 P2.Thanks.
这里有几个定义和符号，我们先看一下：
给定一组原子命题AP。这里没有明确说明，但这通常意味着我们对字母表中具有 AP 幂集的语言感兴趣。所以对于 AP = {a,b,c}，我们的字母表是 Sigma = { {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c }, {a,b,c} }.
如您所见，写出这个幂集字母表可能需要大量工作。出于这个原因，有一种基于命题公式的替代符号。考虑变量 AP 的命题公式 phi。我们可以从 Sigma 中取出一个符号 x，并在 phi 中将 x 中包含的所有原子命题设置为真，将所有其他原子命题设置为假。然后我们评估 phi，它变成真或假。我们可以将 phi 理解为指的是来自 Sigma 的所有 x，其中 phi 的计算结果为真。
例如，公式 phi="a and not b" 指的是符号 {a} 和 {a,c}。公式 phi="a" 引用符号 {a},{a,b},{a,c},{a,b,c}。公式 phi="not a" 引用符号 {},{b},{c},{b,c}。公式 phi="not a and not b and not c" 仅引用符号 {}。公式 phi="true" 指的是来自 Sigma 的所有符号。公式 phi="false" 表示没有符号（不要与符号 {} 混淆）。等等...
此逻辑是您示例中 NFA 边上使用的符号。
如果存在接受 L 的 NFA
如果不在 L 中的每条迹线都有一个坏前缀，即有限前缀 w，使得 w 的无限延续不在L.
如果其错误前缀的语言是常规的，我们称安全性为属性"regular"。请注意，我们在这里处理 "regular" 的两种不同概念，一种用于有限词的语言，另一种用于无限轨迹上的安全属性。
一般方法
您正在处理从安全性的非正式描述 属性 到其错误前缀语言的正式描述的问题。没有关于如何做到这一点的一般规则，但请记住，在直观层面上，安全 属性 意味着 "some bad event never happens"。坏前缀的语言正是那些 "the bad event happens at some point" 的有限词。因此，您的方法是分析 "bad event" 是什么。
（当然，这是模型检查中的一个普遍问题，当从非正式描述到正式模型时，存在无法完美捕捉原始描述的风险。）
考虑 P1：坏事件是 "a becomes valid and afterwards b is valid only finitely many steps and becomes false before c becomes true"。我们可以把它变成稍微详细一点的描述："a becomes valid, afterwards we see some b's but no c's and then we see no b and no c"。我们可以使用这个描述来推导出 "the bad event happens at some point" 的正式定义。我个人觉得正则表达式比 NFA 更直观，所以我会先尝试构建一个正则表达式，然后再从中构建 NFA：
(true)* a (b and not c)* (not b and not c) (true)*
此正则表达式描述了在某些时候发生不良事件的所有有限词。我们在开始和结束时使用 (true)* 因为我们不关心坏事件之前或之后发生的事情。在您的示例中，正则表达式已经非常接近 NFA，一般来说，从此类正则表达式构建 NFA 应该很容易。您可以看到，与显式写出符号相比，基于命题公式的符号使这更加紧凑，例如写 "a" 比写完整的正则表达式 ({a} + {a,b} + {a,c} + {a,b,c}) 更短。
这不是唯一的解决方案，而不是要求先看到(b and not c)*再看到(not b and not c)，要求先看到(not c)*再看到(不是 b 也不是 c)。这将导致正则表达式：
(true)* a (not c)* (not b and not c) (true)*
与第一个解决方案的唯一区别是我们不需要匹配我们看到的第一个（不是 b 而不是 c），我们也可以跳过一些（不是 b 而不是 c），因为它们也匹配（不是c），只要我们最终匹配a（不是b也不是c）。所以在某种程度上，第一个解决方案是更好的解决方案，因为由此产生的 NFA 更具确定性。
考虑 P2：糟糕的事件是有两个 a，使得两者之间的某个点 b 不成立。将其转换为稍微冗长的描述，我们将得到 "we see a, afterwards we see some b's without seeing a, then we reach a point where we see neither b nor a, afterwards we see any symbols until we reach the closing a"。将其转换为 "the bad event happens at some point" 的正则表达式可以得到：
(true)* a (b and not a)* (not b and not a) (true)* a (true)*
同样，这与您示例中的 NFA 非常相似，应该很容易看出如何从这样的表达式构造 NFA。和以前一样，我们也可以通过将 (b and not a)* 放宽为 (not a)* 来获得替代解决方案，唯一的区别是这将允许跳过一些（not b and not a），只要因为我们最终匹配了一个。此外，我们可以将中间的 (true)* 加强为 (not a)*，要求我们匹配第一个结束 a 而不是在匹配结束 a 之前允许跳过一些 a:
(true)* a (not a)* (not b and not a) (not a)* a (true)*
关于州数
既然你问到如何知道状态的数量：我会先尝试获得一些NFA，然后检查它是否可以简化。对于您示例中的 NFA，我看不到进一步减少状态数量的方法，但通常最小化 NFA 是一个难题 (reference)，因此没有有效的算法。当然，如果你得到一个完全确定的自动机，你可以应用最小化DFAs的标准算法。
我们使用 NFA 为安全性 BadPrefixes 建模 property.I 想了解给定的安全性 属性 如何对 NFA 建模。
以下图片供参考。
例如，为了安全 属性 P2，有人可以解释一下如何知道需要多少个状态（解决方案有 4 个）以及在边缘使用哪种逻辑，图 3 和图.4 ，选择边来满足 badprefixes P1 和 P2.Thanks.
这里有几个定义和符号，我们先看一下：
给定一组原子命题AP。这里没有明确说明，但这通常意味着我们对字母表中具有 AP 幂集的语言感兴趣。所以对于 AP = {a,b,c}，我们的字母表是 Sigma = { {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c }, {a,b,c} }.
如您所见，写出这个幂集字母表可能需要大量工作。出于这个原因，有一种基于命题公式的替代符号。考虑变量 AP 的命题公式 phi。我们可以从 Sigma 中取出一个符号 x，并在 phi 中将 x 中包含的所有原子命题设置为真，将所有其他原子命题设置为假。然后我们评估 phi，它变成真或假。我们可以将 phi 理解为指的是来自 Sigma 的所有 x，其中 phi 的计算结果为真。
例如，公式 phi="a and not b" 指的是符号 {a} 和 {a,c}。公式 phi="a" 引用符号 {a},{a,b},{a,c},{a,b,c}。公式 phi="not a" 引用符号 {},{b},{c},{b,c}。公式 phi="not a and not b and not c" 仅引用符号 {}。公式 phi="true" 指的是来自 Sigma 的所有符号。公式 phi="false" 表示没有符号（不要与符号 {} 混淆）。等等...
此逻辑是您示例中 NFA 边上使用的符号。
如果存在接受 L 的 NFA
，我们将有限词上的语言称为 L "regular"
如果不在 L 中的每条迹线都有一个坏前缀，即有限前缀 w，使得 w 的无限延续不在L.
如果其错误前缀的语言是常规的，我们称安全性为属性"regular"。请注意，我们在这里处理 "regular" 的两种不同概念，一种用于有限词的语言，另一种用于无限轨迹上的安全属性。
一般方法
您正在处理从安全性的非正式描述 属性 到其错误前缀语言的正式描述的问题。没有关于如何做到这一点的一般规则，但请记住，在直观层面上，安全 属性 意味着 "some bad event never happens"。坏前缀的语言正是那些 "the bad event happens at some point" 的有限词。因此，您的方法是分析 "bad event" 是什么。
（当然，这是模型检查中的一个普遍问题，当从非正式描述到正式模型时，存在无法完美捕捉原始描述的风险。）
考虑 P1：坏事件是 "a becomes valid and afterwards b is valid only finitely many steps and becomes false before c becomes true"。我们可以把它变成稍微详细一点的描述："a becomes valid, afterwards we see some b's but no c's and then we see no b and no c"。我们可以使用这个描述来推导出 "the bad event happens at some point" 的正式定义。我个人觉得正则表达式比 NFA 更直观，所以我会先尝试构建一个正则表达式，然后再从中构建 NFA：
(true)* a (b and not c)* (not b and not c) (true)*
此正则表达式描述了在某些时候发生不良事件的所有有限词。我们在开始和结束时使用 (true)* 因为我们不关心坏事件之前或之后发生的事情。在您的示例中，正则表达式已经非常接近 NFA，一般来说，从此类正则表达式构建 NFA 应该很容易。您可以看到，与显式写出符号相比，基于命题公式的符号使这更加紧凑，例如写 "a" 比写完整的正则表达式 ({a} + {a,b} + {a,c} + {a,b,c}) 更短。
这不是唯一的解决方案，而不是要求先看到(b and not c)*再看到(not b and not c)，要求先看到(not c)*再看到(不是 b 也不是 c)。这将导致正则表达式：
(true)* a (not c)* (not b and not c) (true)*
与第一个解决方案的唯一区别是我们不需要匹配我们看到的第一个（不是 b 而不是 c），我们也可以跳过一些（不是 b 而不是 c），因为它们也匹配（不是c），只要我们最终匹配a（不是b也不是c）。所以在某种程度上，第一个解决方案是更好的解决方案，因为由此产生的 NFA 更具确定性。
考虑 P2：糟糕的事件是有两个 a，使得两者之间的某个点 b 不成立。将其转换为稍微冗长的描述，我们将得到 "we see a, afterwards we see some b's without seeing a, then we reach a point where we see neither b nor a, afterwards we see any symbols until we reach the closing a"。将其转换为 "the bad event happens at some point" 的正则表达式可以得到：
(true)* a (b and not a)* (not b and not a) (true)* a (true)*
同样，这与您示例中的 NFA 非常相似，应该很容易看出如何从这样的表达式构造 NFA。和以前一样，我们也可以通过将 (b and not a)* 放宽为 (not a)* 来获得替代解决方案，唯一的区别是这将允许跳过一些（not b and not a），只要因为我们最终匹配了一个。此外，我们可以将中间的 (true)* 加强为 (not a)*，要求我们匹配第一个结束 a 而不是在匹配结束 a 之前允许跳过一些 a:
(true)* a (not a)* (not b and not a) (not a)* a (true)*
关于州数
既然你问到如何知道状态的数量：我会先尝试获得一些NFA，然后检查它是否可以简化。对于您示例中的 NFA，我看不到进一步减少状态数量的方法，但通常最小化 NFA 是一个难题 (reference)，因此没有有效的算法。当然，如果你得到一个完全确定的自动机，你可以应用最小化DFAs的标准算法。