gpt4 book ai didi

computer-science - 如何模拟不确定的有限换能器?

转载 作者:行者123 更新时间:2023-12-01 02:33:58 24 4
gpt4 key购买 nike

只需跟踪自动机所处的状态及其在输入字符串中的距离,就可以轻松地在输入字符串上模拟不确定性自动机。但是,如何模拟不确定性转换器(转换器当然可以将输入符号转换为输出符号,并给出输出字符串而不只是布尔值)?似乎这更加复杂,因为我们需要以某种方式跟踪输出字符串,由于不确定性,输出字符串可能会很多。

最佳答案

首先,一些理论。以下是不同的代数结构:


发电机(过渡系统)
受体(自动机)
换能器(机器)


括号内的术语在文献中很常见,可惜它们经常被错误地使用。这些代数结构彼此之间非常相似,并且可以通过大量的小变化从一个转换为另一个或混合。但是,这不应该从它们根本不同的事实中分散注意力:


生成器是一种语言的建设性表示形式,即一组(有限或无限)单词。您不确定地遍历生成器,并以此来生成该语言中的所有单词。
接受者还是用于定义一组单词(语言)的构造,但是每个接受者都代表所有可能单词(有限或无限)的指示符功能。因此,他们将每个单词映射到一个布尔值(可以适当地扩展到一个有限或无限的输出单词,以尝试与换能器进行比较-尽管存在明显的代数差异)。
换能器代表将每个允许的有限输入字映射到有限输出字的功能。


在有限语言的上下文中,接受者和换能器之间的区别变得不太明显,因为接受者可以接受或不接受任何有限词,而不论其长度如何,因此它为每个这样的词产生一个输出词。通过对来自接收器的布尔输出进行分类,可以为每个有限输入字创建一个有限输出字(即,通过给定输入字的每个前缀连接输出)。尽管在机械上是正确的,但这种尝试弥合了这两个概念的尝试仍然扭曲了所涉及的概念。

在无限词语言的上下文中,区别更加明显。 infinite-word automaton无法为给定(无限)输入单词的有限前缀生成输出。这种限制是在整个(无限)单词上定义无限单词接受的结果。结果,接受者将每个输入字映射到布尔值,或者如果首选这样的观点,则将输出字映射到布尔值。相反,换能器(机器)将任何输入字的每个有限前缀映射到相等长度的有限输出字。因此,它们被称为顺序机器,因为它们会逐步反应。

有两种不同类型的传感器:


Mealy machines
Moore machines


Moore机器可以用Mealy机器表示。并非每台Mealy机器都可以由Moore机器代表。在定义和比较这两种类型的换能器方面,文献通常是错误的,请参考原始出版物以获取正确的定义。

因此,这两个定义都是确定性的。限制确定性的原因是:换能器用于控制系统,因此我们想确定性地知道下一个要应用的控制动作应该是什么。这导致确定性换能器成为文献中的标准。

然而,非确定性换能器也可以是有用的,例如,作为多种策略的紧凑表示。但是,在执行它们时,仅遵循一条路径并产生一个输出字,而不是同时产生多个输出字是有意义的(就像在执行过程中产生的非确定性受体的副本一样)。

因此,很明显,换能器的不确定性仿真不符合其预期用途。它代表了一组可供选择的策略(如果在每个单打游戏中都不以固定方式确定,也可以混合使用)。

因此,实际上您必须创建一个(可能不断扩展的)可能的输出单词树,并且很快就会崩溃。本质上,这棵树是生成器(转换系统)的展开,您可以通过将其输入注释的换能器剥离而得到。

关于computer-science - 如何模拟不确定的有限换能器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11213728/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com