2

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

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

图 2.E.2

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

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

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

提前致谢!

4

1 回答 1

2

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

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