论文部分内容阅读
自动机理论是算法描述和分析,计算复杂性理论,可计算性等研究的基础,它为计算理论提供了可靠的数学模型。同样,模糊自动机提供了一种研究和处理包含模糊性的自然语言的有力工具,它必将为基于词的软计算理论提供可靠的形式基础。 本文是在更广泛的代数系统—格半群L上对如下的两类自动机 （Ⅰ） A=（Q,X,Y,δ′）(A=（Q,X,Y,M1）, （Ⅱ） A=（Q,X,Y,δ″σ）（A=（Q,X,Y M2,O）） 作了较深入的讨论和研究。其中,Q为非空有限状态集,X,Y分别为非空有限输入字符和输出字符集,用（X|Y）表示所有长度相同的输入-输出字母表上字符对（x|y）的集合,δ′. Q×X×Y×Q→L为（Ⅰ）的模糊状态转移-输出函数,记为δ′qq′（x|y）,δ′qq′（x|y）表示自动机在当前状态q输入字符x,转移到下一个状态q′输出字符y的程度,M1={M（x|y）|M（x|y）=(mqq′（x|y）,x∈X,y∈Y,q,q′∈Q,mqq′</sub>（x|y）∈L}为（Ⅰ）的转移-输出矩阵;δ″:Q×X×Q→L为（Ⅱ）的模糊状态转移函数,记为δ″qq′（x）,δ″qq′（x）表示自动机在当前状态q输入字符x,转移到下一个状态q′的程度,σ:Q×X×Y→L为（Ⅱ）的模糊输出函数,记为σq（x|y）,σq（x|y）表示自动机在当前状态q输入字符x,输出字符y的程度,M2={M（x）|M（x）=(mqq′（x）),x∈X,q,q′ ,∈Q,mqq′（x）∈L)为（Ⅱ）的转移矩阵,O={O（x|y）|O（x|y）=（σq（x|y））,x∈X,y∈Y,q∈Q,σq（x|y）∈L}为（Ⅱ）的输出矩阵。由于这两类自动机的输入字符和输出字符的长度相同且取值格为格半群,则分别称之为同步格值自动机（完备的同步格值自动机）和同步格值有限自动机（完备的同步格值有限自动机）。 自动机的最小化问题是自动机理论中非常重要的研究课题之一,对于一个己知的自动机,能否快速、准确地找到一个与之等价的最小化的自动机在实际应用中尤为重要。本文主要地在（Ⅰ）和（Ⅱ）这两类格值自动机的最小化方面做了一些讨论,取得了较好的结果,具体如下: （1） 在格半群理论基础上来研究自动机理论; （2） 引入了完备L-Fuzzy矩阵的概念;