基于完备剩余格值逻辑的自动机和文法理论

初步建立基于完备剩余格值逻辑自动机与文法理论的基本框架。引入l值正则文法的概念,证明了任意l值自动机识别的语言等价于某种l值正则文法所生成的语言,反之,任意l值正则文法所生成的语言等价于某种l值自动机识别的语言。获得l值自动机及被l值自动机识别的语言的连接问题刻画。特别地,建立l值和L值泵引理,并得到l值语言的判定性刻画。最后,揭示带ε移动的l值自动机与不带ε移动的l值自动机之间的两个等价关系。     

基于量子逻辑的自动机和文法理论

初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.     

取值于赋值幺半群的加权正则文法语言

正则文法是研究自动机的重要工具。引入取值于赋值幺半群的加权正则文法、加权类正则文法的定义,讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机(WFA)的关系。证明了在赋值幺半群上,已知一个加权正则文法或加权类正则文法,分别存在一个WFA与之等价。定义了可分配的赋值幺半群,证明了在可分配的赋值幺半群上已知一个WFA,存在一个加权正则文法和加权类正则文法与之等价,即证明了可分配的赋值幺半群上加权正则文法、加权类正则文法和WFA在生成语言上等价,并举例说明了赋值幺半群的可分配性不是已知WFA存在与之等价的加权正则文法或加权类正则文法的必要条件。     

基于量子逻辑的确定型正则文法

基于量子逻辑的文法理论是量子计算模型的一个重要研究方向.给出了基于量子逻辑的确定型正则文法的概念,证明了基于量子逻辑的确定型正则文法与基于量子逻辑的确定型自动机的等价性.利用此等价性,给出了量子确定正则语言的代数刻画和层次刻画,并得到量子确定正则语言关于正则运算的封闭性.     

处理图像语言的格点自动机与格点文法

Giammarresi与Restivo在一篇综述中总结出一个关于可识别的图像语言(即2维矩形语言)REC的等价性定理.对比1维字语言的相应结果,其中还缺少关于生成文法的相应一环.提出了一种(矩形的)格点文法,正好弥补了这一缺环.而取代2维on-line tesselation自动机,引入了格点自动机的概念.一方面,它与经典的2元树型自动机更相似,另一方面,它也是格点文法与等价性定理中关于REC的其他描述方式之间的一座桥梁.同时,标准的existential monadic二阶逻辑也被一种更弱的规范框架——positive monadic分划逻辑所取代.由此导出一个新的更完整的关于REC的等价性定理.     

格值树自动机与格值上下文无关树文法的等价性

本文将模糊树自动机和模糊上下文无关树文法的概念推广到格半群上。证明了在接受语言和生成语言的意义下,树自动机和上下文无关树文法是等价的。同时给出了构造正规形式的等价文法的方法。     

模糊Büchi自动机的等价刻画

模糊语言的研究是形式语言研究的焦点之一,然而如何对模糊语言进行刻画甚至更好地分类是其中一个重要研究方向.文章在模糊ω-语言的研究基础上,从模糊逻辑角度研究了模糊ω-正则语言的等价刻画.首先借助广义子集构造方法,证明了任一模糊Büchi自动机与具有分明初始状态和状态转移函数且具有模糊终状态的模糊Büchi自动机是等价的,藉此研究了模糊ω-正则语言的代数刻画和层次刻画,讨论了模糊ω-正则语言关于正则运算的封闭性;其次引入单体二阶(L)ukasiewicz逻辑的概念,给出模糊Büchi自动机识别语言的等价逻辑刻画;最后通过引入ω-星自由和ω-非周期模糊ω-语言,利用“层次化”处理技巧得到了多值逻辑意义下的分类定理,对模糊ω-正则语言给出了一种分类方法.     

格值下推自动机与格值上下文无关文法

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。     

扰动值模糊有限自动机及其语言*

引入扰动值模糊有限自动机及其语言的概念,讨论扰动值模糊有限自动机的状态转移函数的扩张问题,证明3类确定型扰动值模糊有限自动机、非确定型扰动值模糊有限自动机相互等价性,研究扰动值模糊有限自动机的语言关于正则运算的封闭性.     

Lukasiewicz逻辑值上下文无关语言的代数刻画

提出了基于Lukasiewicz逻辑的下推自动机（l-VPDA）的概念,从代数角度研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用模糊状态构造,证明了任意以终状态方式接受模糊语言的l-VPDA与状态转移为经典函数且具有l值模糊终状态的l-VPDA间的相互等价性;并证明任意以空栈方式接受模糊语言的l-VPDA与状态转移除一步转移为模糊的以外,其余都是经典函数的l-VPDA是相互等价的;详细研究了l-值模糊上下文无关语言的代数和层次刻画,以及对于正则运算的封闭性。     

形式语言与自动机中关于ε的一些问题

讨论了形式语言与自动机理论中关于空串ε的一些问题。分析了ε产生式对文法和语言分类的影响;从文法和有限状态自动机的角度讨论了开始符号S和开始状态q0的作用;提出了语言增加或减少ε句子的简单方法;研究了ε-NFA的ε状态转换函数的本质;提出了ε-NFA转换为NFA的新方法,即先将ε-NFA转换为文法形式,消除ε产生式和单产生式后得到正则文法,再将正则文法转换为NFA。并用实际例子进行了验证。     

Algebraic properties of LA-languages

In this study, we introduce the concepts of L-valued regular substitution (LA-substitution), deterministic L-valued regular substitution (DLA-substitution), L-valued fuzzy homomorphism and its inverse images, homomorphism and its inverse images for a lattice-ordered monoid L. We also study the properties of LA-languages and DLA-languages under the above-mentioned algebraic operations. The algebraic characterization of the L-valued regular language is given.     

IFS与L系统的统一描述语言及其分类

为了更高效地表示分形图形,依据形式语言的文法结构及正则表达式的文法规则,通过引入代数运算,提出了一个能够对L系统和迭代函数系统(IFS)统一描述的语言代数系统。根据语言代数系统产生式的文法规则,将此系统的产生式集划分为五类。结合分形理论,此语言代数系统着重将DOL系统、迭代函数系统(IFS)、带凝聚集迭代函数系统(凝聚IFS)、随机迭代函数系统(IFSP)和再归迭代函数系统(RIFS)等进行描述,同时用此系统的正则表达式方程解将分形吸引子进行代数表示,并给出一些实例。通过实例表明,分形图形可以用该语言代数系统简单、明了、高效地表示。     

On regular tree languages and deterministic pushdown automata

The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.     

正规树文法的产生式相交判定

在针对产生式不相交的正规树文法的XML类型检查中,需要对正规树文法的产生式进行相交判定.基于正规树文法的产生式的构成特点,提出了基于自动机的相交判定算法.根据产生式的内容模型即正则表达式,构建相应自动机,判定两个自动机的交是否为空,该算法的时间复杂度为O( ‖ E1‖·‖ E2‖·|∑E1 ∪∑E2 |).实验结果表明,该算法运行正确且高效,可以应用到针对产生式不相交的正规树文法的XML类型检查中.     

Parikh?s theorem: A simple and direct automaton construction

Parikh?s theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free grammar, produces a finite automaton recognizing such a regular language.     

有限自动机可识别语言的基数

利用有向图的邻接矩阵研究有限自动机的可识别语言的基数问题。通过建立有限自动机的可识别语言与其有向图中从初始结点（有限自动机的初始状态）到终止结点（有限自动机的终止状态）的路的一一对应关系,利用邻接矩阵给出了有限自动机的可识别语言的基数公式,研究了两个自动机不等价的充分条件。     

The three-dimensional fuzzy sets and their cut sets

In this paper, a new kind of L-fuzzy set is introduced which is called the three-dimensional fuzzy set. We first put forward four kinds of cut sets on the three-dimensional fuzzy sets which are defined by the 4-valued fuzzy sets. Then, the definitions of 4-valued order nested sets and 4-valued inverse order nested sets are given. Based on them, the decomposition theorems and representation theorems are obtained. Furthermore, the left interval-valued intuitionistic fuzzy sets and the right interval-valued intuitionistic fuzzy sets are introduced. We show that the lattices constructed by these two special L-fuzzy sets are not equivalent to sublattices of lattice constructed by the interval-valued intuitionistic fuzzy sets. Finally, we show that the three-dimensional fuzzy set is equivalent to the left interval-valued intuitionistic fuzzy set or the right interval-valued intuitionistic fuzzy set.