一类交替的ω—有穷自动机和确定的ω—有穷自动机识别能力…

本文提出了一类交替的ω－有穷自动机，即所有状态都是万能的交替的ω－有穷自动机，并采用了构造的方法证明了ω－ＵＡＦＡ和确定的ω－有穷自动机在四种接受条件下接受的ω－语言的等价性。     

关于ω—有穷自动机的两个新的接受条件

至今被公开的ω有穷自动机的接受条件有６个即Ｃ１－Ｃ６，寻找新的接受条件和研究ω－有穷自动机关于新接受条件接受ω－语言能力是ω有穷自动机理论中的一个重要课题。本定义了ω有穷自动机的两个新的接受条件Ｚ１和Ｚ２，并且研究了：（１）ω－Ｕ－ＮＦＡ关于Ｚｉ（ｉ＝１，２）接受ω－语的能力。     

关于交替的ω─有穷自动机的接受条件

到目前为止，交替的ω－有穷自动机的接受条件仅有６种，本文给出了６种新形式的接受条件，并研究了交替的ω－有穷自动机在这些条件下识别语言的能力．最后给出了ω－自动机在各种接受条件下识别的语言类．     

关于有ω-穷自动机的两个新的接受条件*

至今被公开的ω-有穷自动机的接受条件有6个即C₁—C₆，寻找新的接受条件和研究ω-有穷自动机关于新接受条件接受ω-语言的能力是ω-有穷自动机理论中的一个重要课题．本文定义了ω-有穷自动机的两个新的接受条件Z₁和Z₂，并且研究了：(1)ω-U—NFA关于Z_i(i=1,2)接受 ω-语言的能力，得到了 N     

一种新的ω－识别模型

本文提出了一种新的ω－识别模型：ω－循环自动机及其循环接受条件．给出了ω－循环自动机在该接受条件下所接受的ω－语言类的集合表示．     

关于交替的ω—有究自动机的接受条件

到目前为止，交替的ω－有究自动机的接受条件仅有６种，本给出了６种新形式的接受条件，并研究了交替的ω－有究自动机交些条件下识别语言的能力，最后给出了ω－自动机在各种接受条件下识别的语言类。     

ω—正则语言类的一个子类

ω－语言是由有穷字线靖Σ上的一些无穷串组成的集合，被ω－有穷自动机接受的ω－语言称为ω－正则语言，作者曾从集合的角度描述了一类ω－正则语言，而不是传统地从生成或识别的角度来描述这一类正则语言，本文从集合的角度来描棕更为广泛的一类ω－正则语言。     

一种新的ω—识别模型

本文提出了一种新的ω－识别模型：ω－循环自动机及其循环接受条件，给出了ω－循环自动机在该接受条件下所接受的ω－语言类的集合表示。     

ω—正则语言类的一个子类*

ω—语言是由有穷字母表∑上的一些无穷串组成的集合．被ω一有穷自动机接受的ω一语言称为ω一正则语言．作者曾从集合的角度描述了一类ω一正则语言，而不是传统地从生成或识别的角度来描述这一类正则语言．本文从集合的角度来描述更为广泛的一类ω一正则语言．     

ω幂上下文无关语言及其封闭性质

本定义了ω幂上下无关语言ω－ｐ－ｃｆｌ和一类ω下推自动机ω－ｐｄａ，给出了它们的关系，借助于ω时序转换器ω－ＳＴ，讨论了ω－ｐ－ｃｆｌ类的某些封闭性质，证明了对于ω－ｐ－ｃｆｌ类ζ，ξ（δ）＝｛Ｓ（Ａ）｜Ａ∈ζ，Ｓ是一个ω－ＳＴ｝＝｛ｈ２（ｈ＾－１１（Ａ）∩Ｒ）｜Ａ∈ξ，Ｒ是一个ω正规语言，ｈ１是一个同态，以及ｈ２是一个λ无关同态｝。     

几类ω－凸语言族的分层

本文对作者几年来先后在ω－语言族中定义的五类ω－凸语言进行了相应的分层，其结果是：     

模糊识别器与有穷自动机的等价性

针对模糊识别器与有穷自动机的关系,证明了当输入字母表相同时,任给一个模糊识别器,必然存在一个有穷自动机,使得模糊识别器的行为与有穷自动机所接受的语言相同;反之,任给一个有穷自动机,必然存在一个模糊识别器,使得有穷自动机所接受的语言与模糊识别器的行为相同,从而得出它们之间的等价性。     

S广义ω－凸语言

本文通过在Σω上定义半序关系“≤ωｓ，引进了Ｓ广义ω－左凸语言、Ｓ广义ω－右凸语言和Ｓ厂义ω－凸语言的概念，并给出了各类Ｓ广义ω－凸语言与其前缀语言之间的关系；还给出了各类Ｓ厂义ω－凸语言族对布尔运算的封闭性以及各类Ｓ广义ω－凸语言的充分必要条件。     

基于等价关系的有穷自动机最小化方法

主要介绍了有穷自动机的基础知识,研究了有穷自动机的等价性,并在确定型有穷自动机的状态集上引入等价关系,给出了自动机的最小化过程。利用等价归并算法,可以将某一给定的确定型有穷自动机状态集上的等价状态归并掉,生成与其等价的最小化的确定型有穷自动机。     

基于等价关系的有穷自动机最小化方法

主要介绍了有穷自动机的基础知识,研究了有穷自动机的等价性,并在确定型有穷自动机的状态集上引入等价关系,给出了自动机的最小化过程。利用等价归并算法,可以将某一给定的确定型有穷自动机状态集上的等价状态归并掉．生成与其等价的最小化的确定型有穷自动机。     

加权有穷自动机的代数性质

在加权有穷自动机理论基础上,利用强同态的概念,证明两个加权有穷自动机在计算能力上是等价的,并在加权有穷自动机的状态集上建立一种等价关系,得到加权有穷自动机的商自动机,证明加权有穷自动机与其商自动机在计算能力上也是等价的。并通过引入加权有穷自动机的可交换性、分离性、(强)连通性及层的概念,讨论在(强)同态的条件下,两个加权有限状态机之间的可交换性、分离性、(强)连通性及层的关系。关键词：     

基于Moore机器的一般汉字有穷自动机

为了更好地研究汉字信息输入系统,提高汉字输入速度,解决汉字输入的“瓶颈”问题,通过对以西文为背景的经典自动机理论的研究,给出了能够描述汉字有穷自动机所接受语言的正规表达式,并在此基础上引入了具有输出的有穷自动机的概念,具体给出了基于Moore机器的一般汉字有穷自动机的数学模型。     

有穷自动机和正规文法

3.1 有穷自动机 在第二章,我们介绍了生成图式——文法。文法是对语言的有穷说明。在这一章我们将看到有穷地说明无穷语言的另一种方法——识别器。我们将考虑的无疑是最简单的识别器,叫做有穷自动机。有穷自动机(fa)不能定义所有由文法定义的语言,然而我们将证明已定义     

一类ω—正则语言

ω—语言是由有穷字母表∑上的某些无穷串组成的集合。被所谓的ω—有穷自动机接受的ω—语言称为ω—正则语言。在[4]中作者曾从集合的角度给出—ω—语言为ω—正则语言的几个充分条件。在本文作者仍从集合的角度给出一个ω—语言为ω—正则语言的充分条件,即若—ω—凸语言L满足L=adh(pref(L))=pref(L)tail(L),则L是—ω—正则语言。从而,确定了ω—正则语言类的一个子类。     

汉字模糊有穷自动机的研究

汉字的计算机输入是中文信息处理的关键问题之一,而汉字计算机输入的数学模型对汉字的计算机输入的研究有重要的意义.对汉字输入数学模型的分类进行了研究.研究了一般汉字有穷自动机,在此基础上把模糊有穷自动机的概念引入输入模型,并给出汉字模糊有穷自动机的概念.新的模型是以前给出的汉字自动机模型的推广,较之以前的数学模型,能刻画出汉字智能输入、词句输入,表达能力进一步增强,为汉字的智能处理提供了数学模型.