relation - 计算关系的有限状态传感器

Question

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

Let M = <Q, Σ, Δ, δ, q₀, F> be the deterministic finite-state transducer whose transition diagram is given in Figure 2.E.2.

For each of the following relations find a finite-state transducer that computes the relation.

a. { (x, y) | x is in L(M), and y is in Δ* }.
b. { (x, y) | x is in L(M), y is in Δ*, and (x, y) is not in R(M) }.

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

提前致谢!

Answer 1

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

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