函数流导数与Mealy自动机构造方法

理论计算机科学电子笔记160（2006）305-319www.elsevier.com/locate/entcsMealy自动机JJM Rutten1CWI和VUAP.O. Box 94079，1090 GB Amsterdam，荷兰摘要我们引入了函数流导数的概念，将有理表达式的输入导数的概念（Brzozowski 1964）推广到任意输入和输出字母表上的流函数的情况。我们展示了如何通过函数流导数的符号计算从代数特定的流函数构造Mealy自动机。我们针对2进数的代数演算中指定的各种比特流函数详细说明了这种构造。这项工作是一个更大的正在进行的e-ort的一部分，以指定和模型组件连接器电路的（功能和关系on）流。关键词：流函数，函数流导数，Mealy自动机，比特流，二进制算术，2-adic整数。1引言在[7]中，Brzozowski展示了如何通过计算其有限个导数来为有理表达式构建确定性有限自动机，从而将有理语言具有有限个（左）导数的众所周知的事实提升到表达式的符号水平。从那时起，各种应用和generalisations进行了研究。在文献[1]中，Antimirov引入了偏导数的概念，并用它来构造不确定的有限自动机。在[19，20]中，我们用余代数术语重新表述了Brzozowski的形式幂级数任意半环，同时提供了一个generalisation的Antimirov的结果。伦巴第和萨卡洛维奇独立地发现了一个类似的推广形式的幂级数和具有多重性的有理表达式[15，16]。在这里，我们提出了另一个概括Brozowski我们看看确定性的Mealy自动机[9]，输入和输出在任意alpha上，1电子邮件：janr@cwi.nl1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.05.030306JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305赌注（cf.实施例2.4）。我们使用从输入的无限序列到输出的无限序列的流函数来指定它们的行为。我们介绍了（语义）概念的功能流衍生物（第2节），它可以用来构建任何流函数的最小Mealy自动机。函数流导数已经在[17]中以状态（序列函数的）的名义出现。Mealy自动机的最小化也是众所周知的[9]。本文的主要贡献是洞察力，功能流导数往往可以计算sym- bolically从代数表达式，指定流函数。用这种方式，一个Mealy自动机可以通过符号操作从代数表达式中构造出来。我们详细描述了比特流上各种函数的这种构造（0和1的有限序列）。我们在2-adic数的代数中指定比特流函数，并构造Mealy自动机，通过符号计算它们的函数流导数来实现这些函数（第3节至第5节）。一般来说，这会产生有限自动机，但我们也将讨论一些代数表达式族，对于这些代数表达式，构造会产生有限（和最小）自动机。贡献和相关工作将在第6节中讨论。这将包括我们的数字电路设计的建设的相关性的讨论在这里，我们想指出的是，目前的工作是一个更广泛的正在进行的研究工作的一部分，开发模型和规格的组件连接器电路的形式主义在[5]和[4]中，我们使用流上的关系和所谓的约束自动机作为Arbab[ 2 ]的组件连接器演算Reo的模型在那里，我们展示了如何从连接器电路到（关系）流，以及如何从连接器电路到自动机。此外，在[3]中描述了如何从自动机构造电路的初步想法（这相当于从逻辑设计中对众所周知的技术的非平凡概括我们打算将本文的技术推广到组件连接器电路的（约束）自动机的规范和符号构造。2米兰自动机给出了Mealy自动机和流的基本定义。我们介绍了功能流衍生物的概念，并展示了它如何可以被用来实现最小自动机。设A和B是任意集合。一个Mealy自动机（S，φ）由一组状态S和一个转移函数φ：S→（B×S）A组成，其输入在A，输出在B。该函数将状态s0∈S映射为函数φ（s0）：A→（B×S），该函数为每个输入a∈A产生唯一的一对b，s1，由输出b和下一个状态s1组成。（Mealy自动机也被称为顺序机[9]。一般化包括部分的转移函数，并且可以映射到B×S而不是B×S。在最近的参考文献中，后者被称为（子）顺序换能器[18，8]。在余代数术语，Mealy自动机是函子F：Set→Set的余代数关于集合和函数的范畴，对于任何集合S，定义为F（S）=JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305307一（B×S）A.）我们将使用以下符号：一|Bs0s 1 φ（s0）（a）=如果输入和输出取自集合2 ={ 0， 1}，我们称Mealy自动机为二进制。我们通过A ω = { σ}定义任意集合A上的流集合Aω|σ：IN →A}。元素σ∈Aω将由σ =（σ（0），σ（1），σ（2），. . ）.我们定义流σ的流导数为：σJ=（σ（1），σ（2），σ（3），. ）我们称σ（0）为σ的初始值。 我们将使用以下符号，因为一个0，...，an∈A且σ∈ Aω：a0：···：ann：σ =（a0，.，an，σ（0），σ（1），σ（2），. . ）例如，我们有σ=σ（0）：σJ。我们称一个函数f：Aω→Bω为因果函数，如果对任何σ∈Aω，流f（σ）的第n个元素只依赖于σ的前n个元素。更正式地说，f是因果的，如果f（a0：···：an：σ）（n）=f（a0：···：an：τ）（n）对于所有n≥ 0，a0，.，an∈A，σ，τ∈Aω.我们很快就会看到，因果流函数通常是作为对Mealy自动机行为的描述而出现的。注意因果函数的合成也是因果的。（因果函数有时也称为同步函数或字母对字母函数。下面的基本定义引入了函数流导数的概念，稍后将基于此建立一个新的构造Mealy自动机的符号算法。定义2.1[函数流导数]对于因果函数f：Aω→Bω且a∈A，我们定义f的初始输出（在输入a上）为f[a] =f（a：σ）（0），其中σ∈Aω是任意的。我们将f（在输入a上）的函数流导数定义为函数fa：Aω→Bω，对于所有σ∈Aω，定义为fa（σ）=f（a：σ）J。Q注意，在f[a]的定义中，σ的实际值是无关紧要的，因为f是因果的。我们的符号f[a]不应该被理解为：f应用于参数a（这没有意义，因为f接受有限个流作为参数），而只是f（a：σ）（0）的简写。可以说，在（输入的）流σ上，函数流导数fa的作用就像f“设Γ ={f|f：Aω→Bω|f是因果关系。 我们定义一个函数π：Γ→（B×Γ）A，对于f∈Γ和a∈A，通过π（f）（a）=<$f[a]，fa<$（注意当f是时，fa是因果的这给了我们一个（无限）Mealy自动机（Γ，π），Fa|f[a] f308JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）30501接下来，我们使用以下概念来计算π（r，π）自动机（S，φ：S→（B×S）A）和（T，φ：T→（B×T）A）的同态是一个保持转移的函数h：S→T：如果φ（s0）（a）=则;换句话说，s0一|b s1 苏丹ha|bh（s）命题2.2（Γ，π）是一个最终Mealy自动机：对于每个Mealy自动机（S，φ）（输入在A，输出在B），存在唯一同态h：（S，φ）→（Γ，π）。证据对于Mealy自动机（S，φ），我们定义一个函数h：S→Γ。对于s0∈S，我们定义了一个函数h（s0）：Aω→Bω，其中考虑了σ∈Aω和k≥0的（唯一的）相应的跃迁σ（0）|b0的σ（1）|B1σ（k）|BKs0s1· ··sk+1设h（s0）（σ）（k）=bk。证明h（s0）是因果的并不困难，而且这样定义的函数h是一个同态，而且是唯一的。Q我们称流函数h（s0）在s0的（输入-输出）行为之上。对于一个因果函数f∈Γ，我们说自动机S中的一个状态s0实现了f，如果f=h（s0）。在代数中，Mealy自动机的行为通常用A+→B型函数来描述。虽然这个集合同构于最终余代数Γ，但我们更喜欢使用后者，因为它的代数结构更丰富，我们将在后面看到Γ的普适性还可以用另一种方式来表达我们需要以下概念。对于Mealy自动机（S，φ）的状态s0∈S，设s0S表示包含s0且在转换下（对于任何输入）闭合的最小子集。很明显，s0也是（S，φ）的一个子自动机，通过把φ限制到集合s0作为它的转移函数。我们称s0为s0生成的（S，φ）的子自动机。推论2.3（a）对于因果函数f∈Γ，子自动机中的（状态f）f（b）此外，f是实现f的最小Mealy自动机（具有最少的状态数）。证据陈述（a）由以下事实得出：单位函数id：Γ→ Γ是同态。对于（b），设（S，φ）是一个Mealy自动机，并考虑一个实现f的状态s0∈S，即：h（s0）=f，其中h如命题2.2所示。不失一般性，我们可以假设S中的所有状态都可以从s0到达，即，s0(If不，我们只是简单地取S0，而不是S开始。）因为h是一个同态（因此保持了变迁），所以S在h下的像h（S）是一个Γ的子自动机;而且，h（S）=h（s0）<$）=<$h（s0）<$=<$f<$。因此，S的大小至少是f的大小。QJJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305309zs1zs，2zs12根据（Γ，π）的定义，通过反复计算f的所有函数流导数，可以构造出实现f∈Γ的极小Mealy自动机f.在第5节中，我们将描述如何通过符号计算从代数指定的流函数构造二元自动机。例2.4我们用一个简单的例子来说明上面的概念和结果。考虑一个二元Mealy自动机，状态空间S ={s0，s1，s2}，转移函数f：S→（2×S）2由下图定义：0 |00 |11 |00 |01|1分，1 |1它是一个单比特二进制计数器。从状态s0开始，当输入偶数个1时，该自动机输出0请注意，我们故意引入了一些冗余：状态s0和s2是等价的，并且可以被识别（正如我们将在下面看到的）。接下来考虑函数f，g：2ω→ 2ω，定义为，对于σ∈2ω，k≥0，由⎧如果（σ（0），.，σ（k））包含偶数个1f（σ）（k）=01否则且g（σ）（k）= 1−f（σ）（k）。我们有以下初始输出和函数流衍生物：f[0]= 0，f [1]= 1，g [0]= 1，g [1]= 0，f0=f，f1=g，g0=g，g1=f由此得出，实现f的最小Mealy自动机由下式给出：f0|01|1f，1|00 |1zg，，还注意到，对于命题2.2中的h，我们有h（s0）=h（s2）=f和h（s1）=g和0 |00 |11 |00 |00 |01 |10 |11|1分，1 |1zs，s。Hf，1 |0zg，，因此，h将S=S0映射到它的最小化fr，在右边。Q正如我们在引言中提到的，函数流导数的概念已经出现在[17]中，并在那里被称为状态。它也是从A到B的函数的导数（或逆）的经典概念的变体[9]。 也是命题zs0zs0310JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）3052.2和推论2.3本质上是经典结果的重新表述。本文件的con-term的观察，功能流导数可以象征性地计算从代数表达式，指定流函数。在第5节中，我们将使用我们接下来介绍的2-adic数的代数来32-adic算子在第5节中，我们将通过计算流函数的函数导数来构造最小Mealy自动机虽然这种方法适用于任意字母表上的自动机和流函数，但我们将说明二进制自动机和比特流函数的更具体地说，我们将研究比特流函数，这些比特流函数是根据比特流上的一些基本运算符来指定的，即所谓的2-adic运算符，我们将在本节中介绍。（其他类型的运算符将在结论中提及。）设2ω是比特流的集合：0和1的有限序列在介绍2-adic运算符之前，我们首先回顾一下（参见[13，10]）位流也被称为2-adic数，因为它们可以被视为普通的二进制表示，号码对于分母为奇数的有理数，其工作原理如下。本文定义了当a_q∈ Q_q ={n/（2m+1）}时B（q）的一个二进制表示|n，m∈Z}作为满足以下方程组的唯一流（每个q一个）：B（q）J=B（（q-odd（q））/2），B（q）（0）=odd（q）其中，如果n是奇数，则奇数（n/2 m+ 1）= 1，如果n是偶数，则奇数（n/2m+1）= 0。 这些方程通过指定流导数B（q）J和初始值B（q）（0）来定义流B（q因此，它们被称为流微分方程（见[20]的一个概述）。 不难看出，上面的方程定义了一个不确定性，B：Qω →2ω。（定义不适用于所有情况denominator.）这里有一些例子;注意，最小有效位总是在左边：B（13）=（1，0，1，1，0，0，0，. . ），B（− 5）=（1，1，0，1，1，... ），以及B（1/5）=（1，0，1，1，0，0，1，1，0，0，1，1，0，0，. . . ）. 通常，正整数的比特流以0结束，负整数的比特流以1结束，并且有理数的比特流最终是周期性的(All这是众所周知的;参见上述参考文献。接下来我们介绍2-adic运算符，用它可以以与普通数相同的方式计算比特流。我们需要以下几种材料。2 ={ 0， 1}上的布尔运算符定义如下，对于所有a，b∈2，像往 常 一 样 ： ab= max{a ， b} ， ab= min{a ， b} ， <$a = 1−a ， ab= （ a<$b ）<$（<$ab）（异或）。传统上，2-adic算子是根据形式幂级数定义的（参见上述参考文献）。在这里，我们将2-adic运算符简单地作为从比特流到比特流的函数，并通过流微分方程来定义它们这些定义与经典定义是等价的，但有一个优点，即在它们的帮助下，可以立即计算函数流导数，这些导数将用于构造二进制自动机（第二节）。JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305311第5段）。对于比特流σ、τ∈ 2 ω，我们将σ + τ、−σ、σ×τ和1/σ定义为满足以下方程组 的 唯 一 流 （ 我 们 使 用 以 下 符 号 ： 对 于 a ∈ 2 ， 我 们 写 [a]= （ a ， 0 ， 0 ，0，.. . ））：衍生物：初始值：用户名：（σ+τ）J=（σJ+τJ）+[σ（0）<$τ（0）]（σ+τ）（0）=σ（0）<$τ（0）总和（−σ）J= −（σJ+[σ（0）]）（−σ）（0）=σ（0）减去（σ×τ）J=（σJ×τ）+（[σ（0）]×τJ）（σ×τ）（0）=σ（0）<$τ（0）产品（1/σ）J=−（σJ×（1/σ））（1/σ）（0）= 1逆像往常一样，我们将τ×（1/σ）写成τ /σ;注意1/σ仅定义为σ（0）= 1时的σ。不难证明这个系统唯一地决定了这四个算子（详见[21]），并且它们是因果的。简要说明了这些方程的形式。计算σ+τ之和通过逐元素加法，但是附带条件是“过流”位被传递到更高阶的位置（也就是说，流中的下一个右边）。这解释了初始值（σ+τ）（0）=σ（0）<$τ（0）和“进位”项的存在[σ（0）<$τ（0）]在导数（σ+τ）J中。−σ的定义（也称为二两边的值意味着σ（0）<$（（−σ）（0））= 0，因此（−σ）（0）=σ（0）;两边求导意味着σJ+（−σ）J+ [σ（0）] = [0]，由此得出−σ的微分方程的形式。乘法的定义是：移位和加法。最后，逆的定义来自于对任何σ ∈ 2 ω且σ（0）= 1的σ ×（1 /σ）= [1]的读者熟悉有理表达式的输入导数的定义”[7]“我会看到一个很好的例子。例如，我们这里只有一种类型的导数，而对于字母表A上的有理表达式E，我们对每个a∈A都有一个输入导数Ea。(As我们在第2节中已经看到，关于输入的导数在函数流导数的定义中确实起了作用。） 但也有相似之处。例如，上面乘积的导数与有理表达式的级联乘积的输入导数非常相似：（E×F）a=（Ea×F）+（o（E）×Fa）。关于这两种类型的衍生工具的共同基础的解释，我们参考[20]。4一点2进微积分我们简要回顾了2-adic算子的一些基本性质，这些性质对第5节的计算很有用。众所周知，2ω与2-adic算子，是一个交换环（和整域）。所以我们有通常的和与积的交换性，结合性和分配性定律。所以我们有常数[0]=（0，0，0，. . ）和[1]=（1，0，0，.. . ）.由于（1，0，0，0，. . ）+（1，1，1，. . ）=的（0，0，0，.. . ），我们有−[1]=（1，1，1，. . ）. 我们通常只写0、1和-1312JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305[0]、[1]和-[1];上下文应该清楚我们是在谈论流还是数字。为了公式化一些进一步的性质，我们引入另一个常数：X =（0，1，0，0，0，.. . ），它扮演形式变量的角色（如在形式幂级数中）。下面是一些有用的恒等式。我曾为他们的事迹而骄傲，他们的事迹，我曾为他们的事迹而骄傲。引理4.1我们有导数：1 J= 0 J= 0，（−1）J= −1，XJ= 1，初值：0（0）= X（0）= 0，1（0）= −1（0）= 1。 对于σ，τ∈ 2 ω且n≥ 0：X×σ =（0，σ（0），σ（1），σ（2），. .. ），（X×σ）J=σ，（−X×σ）J= −σ，（−σ）J=σJ−σ，σ+σ=X×σ，以及⎧如果σ（0）= 0，则为<$σJ×（σ×τ）J=（σ/τ）J=如果σ（0）= 1，则为σJ×τ+ τ j⎧如果σ（0）= 0且τ（0）= 1，则为σJ/τ如果σ（0）= 1且τ（0）= 1，则为（σJ−τJ）/τ（一）（二）直接推论是X2 =（0，0，1，0，0，. ），X3=（0，0，0，1，0，0，.. . 特别可爱的是身份，如1+1 =X，Xn+Xn=Xn+1和（Xn+1）J=Xn。使用常数X，我们定义以下概念。定义4.2我们称流π = c0 + c1X + c2X2+···+ckXk为多项式，其中所有ci都是0、1或−1。我们定义deg（π）=k，如果ck= 0。我们称σ∈2ω有理数，如果σ=π/ρ，对于多项式π和ρ，ρ（0）= 1。Q请注意，在上述定义中，允许负系数。具体地，也可以是− 1 =（1，1，1，. . ）被认为是多项式。对于有理数流的一个例子，将函数B：Q_n→2ω从有理数流3中取出来，它是一个相对于有理数流的函数(with奇数分母）其二进制表示。因为B（1）= [1]，B（2）=X，并且B与和、减、积和逆的算子交换（换句话说，B是整环的同态），因此B（q）是有理数对于所有q∈ Q∈ m，对于σ∈2ω，n≥0，定义σ的n阶导数σ（n）为σ（0）=σ和σ（n+1）=（σ（n））J.下面的命题是Brzozowski [7]观察到的有理表达式只有有限多个不同的输入的变化衍生物.命题4.3一个理性流只有有限个不同的流导数。证据考虑多项式π，ρ（其中ρ（0）= 1）。根据恒等式（2），并且因为deg（πJ−ρJ）≤M= max{deg（π），deg（ρ）}，所以对于所有n≥0，对于次数deg（κ）≤M的某个多项式κ，n阶导数（π/ρ）（n）的形式为κ/ρ。由于只有有限个不同的多项式，命题如下。这个命题等价于前面提到的众所周知的事实，即有理数的二进制表示（分母为JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305313奇数）最终314JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305周期性的命题4.3关于流导数的公式在第5节中特别有用。在那里，它将被用来表明某些流函数只有有限多个函数流导数，因此，会产生一个有限（和最小）的Mealy自动机。为了获得一些计算流导数的经验，我们以计算有理数（具有奇数分母）q的二元表示B（q）的标准形来结束本节。我们将使用以下符号，对于ai，bj∈2：a0···ak（b0···bl）=（a0，.，ak，b0，. b1，b0，. b1，b0，. bl，.. . ）例如，我们计算5、-5和1/ 5的二进制表示。对于整数，事情非常简单：B（5）=B（1 + 22）=B（1）+B（2）2= 1 +X2= 101（0）B（−5）=−B（5）=− 1−X2 = 1 +X−X3= 110（1）其中我们使用−Xk=Xk−Xk+1，所有k≥0。 对于B（1/ 5）= 1/B（5）= 1/ 1+X2，我们使用第3节中的定义微分方程和引理4.1中的一些恒等式来计算1/1+X2的重导数。特别地，我们将在下面使用（1 +X2）J=（1）J+（X2）J+ [（1）（0）<$（X2）（0）] = 0 +X+0=X（−1−X）J=（−1）J+（−X）J+ [（−1）（0）<$（−X）（0）] =（−1）+（−1）+ 0 =−X1/ 1+X2的重复导数如下：（1/ 1+X2）J=（1J−（1 +X2）J）/1+X2=−X/ 1+X2（−X/1+X2）J= −1/1+X2（−1/ 1+X2）J=（（−1）J−（1 +X2）J）/1+X2=（−1−X）/1+X2（（−1−X）/1+X2）J=（（−1−X）J−（1 +X2）J）/1+X2=（（−X）−（X））/1+X2= −X2/ 1+X2（−X2/1+X2）J= −X/1+X2这些都是1/ 1+X2的不同导数。取它们的初始值，并利用σ=σ（0）：σJ的事实，对于任何σ∈2ω，我们发现B（1/ 5）= 1（0 110）。5二进制自动机在定义2.1中，我们引入了函数流导数的新概念。本节包含了我们的主要贡献：我们展示了如何使用函数流导数来构造最小Mealy自动机。我们将提出一些例子和一个更系统但相当适度的一般结果。(All这将是关于比特流函数和二进制Mealy自动机，但我们重复JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305315我们的方法比这更一般;其他情况将在第6节讨论。）我们将使用以下恒等式：对所有σ∈2ω，0：σ=X×σ，1：σ= 1 +（X×σ）回想一下定义2.1中因果函数f的函数流导数的定义：2ω→ 2ω，对于所有σ∈2ω：f0（σ）=f（0：σ）J，f1（σ）=f（1：σ）J，利用上面的两个恒等式，我们得到以下公式：对所有σ∈2ω，f0（σ）=f（X×σ）J，f1（σ）=f（1+（X×σ））J此外，我们将使用以下符号表示重复函数流导数：对于w∈ 2和a∈ 2，我们定义fε=f（其中ε是空词）和fwa=（fw）a。这是我们建筑的第一个例子 考虑以下函数f：2 ω→ 2 ω：f（σ）=（1+X）×σ(Note 在该表达式中，X表示常量流（0，1，0，0，0，. . ），σ是函数变量。）在第3节的术语中，该函数将2进数σ∈2ω乘以1 +X=B（3），自然数3的二进制表示。注意f是因果函数，如前所述，让Γ表示从2ω到2ω的所有因果函数的集合。回想一下（推论2.3），由f生成的Γ的子自动机是实现f的最小Mealy自动机。我们构造通过计算f的重复函数流导数（使用第3节中的定义f0（σ）=f（X×σ）J=（（1+X）×（X×σ））J=（（1+X）J×（X×σ））+（X×σ）J [注意（1+X）（0）=1]=（X×σ）+σ=f（σ）f1（σ）=f（1+（X×σ））J=（（1+X）×（1+（X×σ）J=（（1+X）J×（1+（X×σ）+（1+（X×σ））J=1 +（X×σ）+σ=f（σ）+ 1f10（σ）=f1（X×σ））J=（1+X）×（X×σ））+1）J=（（1+X）×（X×σ））J+1J[因为（（1+X）×（X×σ））（0）<$1（0）= 0]=f（σ）f11（σ）=f1（1+（X×σ））J=（1+X）×（1+（X×σ）+1）J=（（1+X）×（1+（X×σ）J+1J +1=f1（σ）+1 =f（σ）+1 +1 =f（σ）+Xf110（σ）=f11（X×σ）J=（f（X×σ）+X）J=f（X×σ）J+1 =f1（σ）f111（σ）=f11（1+（X×σ））J=（f（1+（X×σ））+X）J=f（1+（X×σ））J+1 =f11（σ）316JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305zf_11计算进一步的导数不会产生任何新的函数，因此自动机f 转换由初始输出给出，其计算如下（下面的σ是任意流）：f[0] =f（0：σ）（0）=f（X×σ）（0）=（（1 +X）×（X×σ））（0）= 0f[1]=f（1：σ）（0）=f（1+（X×σ））（0）=（（1+X）×（1+（X×σ）（0）= 1类似地，我们计算f1[0] = 1，f1[1] = 0，f11[0] = 0和f11[1] = 1。所以我们找到了f的以下最小自动机：0 |01 |1、、、z_1|01 |1F0 |1f1，_0 |0对于第二个例子，考虑函数g：2ω→ 2ω，对于σ∈2ω，定义为：g（σ）=σ×（1/ 1−X−X2）它将2进数σ乘以−1/ 5，因为B（−1/ 5）= 1/ 1−X−X2。计算g的函数流导数给出以下不同的函数（省略细节）：g1（σ）=g（σ）+（（1+X）/1−X−X2）g10（σ）=g（σ）+（X2/1−X−X2）g11（σ）=g（σ）+（X/1−X−X2）g101（σ）=g（σ）+（（1+X2）/1−X−X2）g110（σ）=g（σ）+（1/ 1−X−X2）在计算了相应的初始输出后，我们发现下面的最小Mealy自动机实现了g：0 |01 |1 J0 |11 |00|11个月，1|00 |00 |11 |0zg，，g，tzzgg，t1011|1十，，1 |1110|0110GJJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305317我们的第三个也是最后一个例子说明了我们的方法也适用于与任意有理数相乘。我们考虑函数h：2ω→ 2ω，对于σ∈2ω，定义为：h（σ）=σ×（1 +X/ 1−X−X2）318JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）3051它将2进数σ乘以−3/ 5。我们没有提到任何细节，而只是给出了结果自动机的状态空间，它和以前一样是通过重复计算h的函数流导数而获得的。它由所有表达式组成h（σ）+（−E/1−X−X2），其中E∈ {0， 1，X， 1+X，X2， 1+X2，X+X2，1+X+X2}因此，一个自动机得到8个状态。上面的过程总是产生一个有限自动机的功能如下形式。定理5.1函数h：2 ω→ 2 ω的形式为h（σ）= σ×φ，对所有的σ∈ 2 ω和固定有理流φ，只有有限个不同的函数流导数。因此，h是实现h的最小有限自动机。证据这是命题4.3的直接结果：理性流只有有限多个不同的流导数。设φ=α/β，对于多项式流α，β。可以证明，对于次数为deg（γ）≤deg（α）+ deg（β）的多项式γ，h的任何重复函数流导数总是h（σ）+（γ/β）的形式。这样的功能只有无限多Q这个定理有各种简单的推广，这里省略了。例如，对于固定有理流φ和φ，它也适用于形式h（σ）=（σ×φ）+φ的函数。同样，对于具有多个输入和多个输出的函数，也可以很容易地公式化一个类似的(See第6节讨论David de Oliveira Costa和Helle Hvid Hansen正在进行的工作，关于定理基础算法的实现5.1.例如，我们上面的最后一个例子是计算机生成的。有趣的是，实验数据现在已经导致了许多关于所得到的自动机的状态空间的大小和结构的描述在本节的结论中，我们看两个例子，说明我们的构造不限于定理5.1形式的函数。设h（σ）=−σ，对所有σ∈2ω.计算导数给出h0（σ）=h（X×σ）J=（−（X×σ））J= −σ=h（σ）h1（σ）=h（1+（X×σ））J=（−（1+（X×σ）J=−（（1+（X×σ））J+1）=−（σ+1）h10（σ）=（−（（X×σ）+ 1））J= −（X×σ）+ 1）J+1）=−（σ+ 1）=h1（σ）h11（σ）=（−（1 +（X×σ）+1））J=（−（（X×σ）+X））J=−（σ+1）=h1（σ）计算初始输出，然后给出以下2-adic minus的最小实现：0 |0H0 |11|1小时，秒，1 |0JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305319我们的下一个也是最后一个例子表明，在自动机领域，并非一切都是有限的。令i：2ω→ 2ω定义为：对于所有的σ∈2ω，i（σ）= 1/（1−（X×σ））。计算函数流导数给出i0（σ）=（1/（1−（X×（X×σ）J=（X×σ）/（1−（X2×σ））i00（σ）=（（X×（X×σ））/（1−（X2×（X×σ）J=（X×σ）/（1−（X3×σ））通过归纳，有i0n（σ）=（X×σ）/（1−（Xn+1×σ）），对所有n≥1。 由于所有这些函数都是不同的（只需取σ = 1作为参数），并且由于i是实现i的最小自动机，因此不存在实现2-adic除法运算的有限自动机。虽然这种类型的否定结果已经存在，但上面的最后一个例子提供了一种新的和非常普遍的证明方法。6讨论和相关工作贡献：（a）观察到所有因果流函数的集合是一个最终的Mealy自动机，其余代数结构由（初始值和）函数流导数的概念给出;（b）从代数特定的因果函数，特别是2-adic算术比特流函数符号构造最小Mealy自动机的新算法。其他二元代数：在[21]中，我们研究了2ω上的许多其他代数结构，每次都通过流微分方程定义代数的算子。因此，通过函数流导数构造Mealy自动机，原则上适用于每个代数中指定的函数。更有趣的是，这同样适用于由所谓的混合表达式指定的函数，其中来自不同代数的运算符一起使用。我们在这里没有空间再列举更多的例子。一般来说，所得到的自动机将是无限的，但对于某些函数类，可以证明可以得到有限自动机。其他字母：函数流导数的概念定义为函数-流上的任意字母。有一个流函数的代数，其中的算子是通过流微分方程定义的，这似乎是应用我们的构造的基础。我们希望在其他代数中可以找到进一步的应用，例如在函数式编程语言中使用。数字电路：众所周知，如何从二进制Mealy自动机中构造数字电路（参见例如[14]的经典参考文献）。因此，可以从二进制流函数的代数规范开始，然后使用我们的构造（的适当实现）来获得Mealy自动机，最后使用标准技术从Mealy自动机构造相应的数字电路。总而言之，这将提供一条从（某些）算术函数的代数规范到相应硬件实现的全自动路径。320JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305请注意，二进制Mealy自动机的极小性结果也与电路有关。特别地，电路为了实现功能规范所需的存储单元（一位寄存器）的最小数量由相应的最小自动机的状态数这样，我们可以使用定理5.1来计算实现算术函数所需的寄存器数量的下限（关于这一点，我们知道的不多[12，22]）。实现：对于诸如2-adic数的代数，Mealy自动机从代数表达式的构造在许多情况下可以自动化。为此，我们必须比在这里更精确地区分句法和语义特别是，一个人必须减少代数表达式的正规形式，以决定是否功能的衍生物导致新的状态或没有。目前，Helle Hvid Hansen和David de Oliveira Costa正在进一步分析和实现我们的构造，用于二进制算术中的某些函数类。相关工作：在[7]中，有理表达式的导数被用来在任意（输入）字母表上获得（摩尔风格）自动机同一篇论文还展示了如何应用该构造来获得任意输入字母表和固定输出字母表2 ={ 0， 1}上的Mealy自动机。有两个主要的区别：（i）我们的方法适用于任意的输出字母表;（ii）我们使用（代数表达式表示）流函数而不是有理表达式（表示形式语言）来指定我们的自动机的行为。后一点也与（输入和）输出都是二进制的情况有关，这种情况由[7]覆盖。正如我们所看到的，来自二进制算术的许多运算符可以很容易地在比特流的2-adic代数中指定，而使用有理表达式（在字母表2）充其量是不方便的，而且往往是不可能的。似乎没有太多的文献从代数特定的流函数中构造Mealy automata。大多数方法使用逻辑规范形式主义（例如参见[6，11]）。在这里，我们从输入和输出流上的逻辑特定关系（有时称为流要求）开始，目标是找到至少一个Mealy自动机（从许多可能的自动机中），其行为满足要求。在这里，我们从一个代数指定的函数开始，并构造实现它的唯一（最小）自动机。确认非常感谢Helle Hvid Hansen对本文早期版本的各种评论引用[1] V. Antimirov. 正则表达式的偏导数和有限自动机构造。理论计算机科学，155：291JJM Rutten/Electronic Notes in Theoretical Computer Science 160（2006）305321[2] F.阿巴布Reo：一个基于通道的组件组合协调模型。计算机科学中的数学结构，14：329[3] F. 阿 巴 布 角 Baier ， F. de Boer ， J. Rutten ， and M. Sirjani. Reo 电 路 的 合 成 。 在 Proceedings ofCoordination 2005中，LNCS的第3454卷，第236-251页。施普林格，2005年。[4] F.阿巴布角Baier，J. Rutten，and M. Sirjani. 用约束自动机对Reo中的组件连接器进行建模。2003年FOCLASA会议记录，ENTCS第97卷。Elsevier，2003年。 扩展版本将出现在计算机编程科学，2005年[5] F. Arbab和J.J.M.M. 拉顿分量连接符的共归纳演算。In M. 韦辛，D. Pattinson和R. Hennicker，编辑，Proceedings of WADT 2002，Volume 2755 ofLNCS，pages35-56. Springer，2003年。[6] A. Aziz，F.巴拉林河Brayton和A.桑乔瓦尼 使用S1S的顺序合成。 IEEE Transactions on Computer AidedDesign of Integrated Circuits and Systems，19（10）：1149[7] J.A. Brzozowski. 正则表达式的导数。 Journal of the ACM，11（4）：481[8] 克里斯蒂安·曹·楚鲁特。最小化等效换能器：综述。理论计算机科学，292：131[9] S.艾伦伯格自动机、语言和机器（A卷）纯粹数学和应用数学。中国科学院出版社，1974年.[10] M. Goresky和A.克拉珀反馈移位寄存器、带存储器的组合器和2-adic跨度。Journal of Cryptology，10：111[11]T. Henzinger，S.克里希南岛Kupferman和F.芒 未初始化系统的合成。 在ICALP'02会议录施普林格，2002年。[12] E.L. 约翰逊和M.A. 卡里姆 数字化设计 PWS出版社，1987年。[1