relation - 计算关系的有限状态转换器

Question

来自http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-twoli1.html#30007-23021r2.2.4：

令 M = <Q, Σ, Δ, δ, q ₀ , F> 为确定性有限状态换能器，其转移图如图 2.E.2 所示。

对于以下每个关系，找到一个计算关系的有限状态换能器。

一个。{ (x, y) | x 在 L(M) 中，y 在 Δ* } 中。
湾。{ (x, y) | x 在 L(M) 中，y 在 Δ* 中，并且 (x, y) 不在 R(M) } 中。

是的，这是硬件，但我一直在努力解决这些问题，至少可以使用指针。如果你想创建自己的 c. 和/或 d. 示例只是为了向我展示如何做到这一点，而不是引导我找到 a 的答案。和 b。那么显然我对此很好。

提前致谢！

Answer 1

由于您没有说明到目前为止您取得了哪些进展，我将假设您根本没有取得任何进展，并将就如何解决此类问题提供总体指导。

• 首先，检查转换图。你明白所有符号的含义吗？请注意，传感器被描述为确定性的。你明白那是什么意思吗？让自己相信转换图中描述的转换器实际上是确定性的。追踪它；尝试了解传感器接受哪些输入以及它给出的输出。
• 接下来，找出这个换能器的 L(M)、Δ 和 R(M) 是什么，因为问题涉及到它们。你知道这些符号是什么意思吗？
• 你知道换能器计算某种关系意味着什么吗？你了解{ (x, y) | ... } 用于描述关系的符号？
• 您能否修改转换图以消除 ε/0 转换并将其合并到相邻的转换中（然后可能在单个转换中输出多个符号）？（恕我直言，这可以帮助创建其他接受相同输入语言的转换器。在这种情况下，部分b比部分a 更重要。）
• 以独立于原始传感器的方式为自己描述需要创建的传感器。这些传感器是确定性的吗？
• 为这些传感器创建转换图。