正规文法与有限自动机的等价性研究

通过证明正规文法和有限自动机之间的等价性定理,给出正规文法和有限自动机之间的等价构造方法。     

有界Petri网的最小化化简

给出了Petri网的语言等价性概念和有界Petri网的最小化概念；证明了有限状态自动机、有界Petri网、正规文法的等价性，给出了它们之间等价转换的算法；分析了有界Petri网的化简过程，并给出了有界Petri网最小化化简的算法，为有界Petri网的自动化化简提供了方法。     

右线性文法与有限自动机等价性的一个新证明

迄今为止,左、右线性文法与有限自动机的等价性都是通过相互模拟构造来证明的。文章首先引入字母表上的右线性方程组及其最小解的概念,证明了最小解的存在性与有效可解性,描述了最小解的结构;其次通过右线性方程组及其最小解,证明了右线性文法与有限自动机的等价性。完全类似地,可以引入字母表上的左线性方程组及其最小解,并且证明左线性文...     

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

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

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

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

正规语言闭包运算的Petri网构造方法

Petri网语言与Chomsky文法体系之间的关系已有了一些结论,已经证明正规语言是Petri网语言的一个子类。相关文献中给出了一种Petri网子类——恰当终结的标准Petri网,并且已经证明恰当终结的标准Petri网语言与正规语言的等价性。在此基础上,研究了正规表达式中Kleene闭包运算“*”的Petri网构造方法,分别给出了Kleene闭包运算“*”的ε-空标注和无ε-空标注Petri网模型的构造方法。该构造方法可由产生正规语言L的网模型直接得到产生正规语言L*的网模型。证明了对于恰当终结的标准Petri网,正规语言闭包运算“*”的构造是封闭的。     

正规文法生成算法及其实现

本文给出了由正规式V生成有限自动机和正规文法的综合算法，并用PAS－CAL语言实现了该算法，具有很好的实用价值。     

广义文法

本文将定义一种新的文法——广义文法,并给出由给定广义文法构造相应标准文法的算法和判定一类广义文法的等价性的算法,最后给出广义方法的一个简单应用例子。 形式语言的文法,不仅是描述程序设计语言的工具,而且是描述程序理论、模式识别、过程控制和生物理论等各方面问题的强有力的工具。因此,扩充文法的表示形式,使之更适应于各方面的应用是有益处的。     

量子自动机的刻画

澄清了各类量子自动机之间的相互关系,并给出了量子自动机的各种等价刻画定理.引入G-量子自动机、g-量子自动机、(广义)量子自动机及G-量子文法和g-量子文法,并阐明了它们与其他量子自动机之间的等价关系.在一定条件下讨论了G(g)-量子自动机与G(g)-量子文法的等价性,从而解决了关于量子文法产生量子正规语言的问题.讨论了量子语言与正规语言的关系,特别是回答了Gudder提出的两个公开问题.最后,给出了一种减少状态空间维数的方法.     

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

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

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

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

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

初步建立了具有某种分配律的扩展格序效应代数和格序QMV代数这两种unsharp量子结构上的自动机与文法理论的基本框架。引入了ε-值正则文法的概念,证明了任意ε-值自动机识别的语言等价于某种ε-值正则文法所生成的语言;反之,任意[ε]-值正则文法所生成的语言等价于某种ε-值自动机识别的语言。讨论了ε-值正则语言在和、连接及反转运算下的封闭性质。     

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

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

计算科学的新领域：DNA计算（Ⅱ）

DNA计算是应用分子生物技术进行计算的新方法。从理论上研究DNA计算方法，有利于推动理论计算科学的发展。本系列文章应用形式语言及自动机理论技术，系统地探讨了DNA分子的可计算性及其计算能力。本文主要介绍DNA分子粘接计算模型的文法结构和计算方法，探讨了不同粘接计算模型的计算能力，并证明了DNA有穷自动机与正规文法的等价性。     

赋权型自动机的不同模型研究

自动机理论是理论计算机科学的基础理论之一,在很多领域自动机有着广泛的应用,有穷状态自动机是正则语言的识别机器,通常分为确定型与非确定型两种模型,其识别语言的能力是等价的。赋权自动机是另一类重要的自动机模型,自动机的每条转移规则和状态可以赋以某一代数结构上的某一数值,从而可以计算输入字符串的权值。任何有穷状态自动机都可以视为一特殊赋权自动机,因此赋权自动机功能更强大,应用更为广泛。     

Controlled finite automata

This paper discusses finite automata regulated by control languages over their states and transition rules. It proves that under both regulations, regular-controlled finite automata and context-free-controlled finite automata characterize the family of regular languages and the family of context-free languages, respectively. It also establishes conditions under which any state-controlled finite automaton can be turned into an equivalent transition-controlled finite automaton and vice versa. The paper also demonstrates a close relation between these automata and programmed grammars. Indeed, it proves that finite automata controlled by languages generated by propagating programmed grammars with appearance checking are computationally complete. In fact, it demonstrates that this computational completeness holds even in terms of these automata with a reduced number of states.     

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata are discussed. The notions of intuitionistic fuzzy recognizer, complete accessible intuitionistic fuzzy recognizer, intuitionistic fuzzy finite automata, deterministic intuitionistic fuzzy finite automata, and intuitionistic fuzzy language are introduced. It is shown that the languages recognized by intuitionistic fuzzy recognizer are regular, and the intuitionistic fuzzy languages recognized by the intuitionistic fuzzy finite automaton and the intuitionistic fuzzy languages recognized by deterministic intuitionistic fuzzy finite automaton are equivalent. This work is supported by National Science Foundation of China (Grant No.10571112), “TRAPOYT” of China and National 973 Foundation Research Program(Grant No.2002CB312200).     

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.