● 摘要
自动机性质的研究是自动机理论的中的一个重要课题. 文献[6,7,8]在广泛的代数系统—格半群的意义下给出了一个新的自动机模型, 即格值有限自动机, 在格半群上研究了自动机及其接受的语言的性质, 给出了格值自动机比模糊自动机和经典自动机具有更强的计算能力. 因此, 对格值自动机及其接受语言的性质的研究就显得更为重要.
本文在[6,7,8,17,19]的基础上研究了格值自动机及其接受的语言的代数性质、逼近性质, 并进一步讨论了格值正则语言截集的代数性质和逼近性质.
自动机及其接受语言的代数性质是指自动机及其接受语言关于交、并、补、闭包、反转、同态、逆同态、商等代数运算的封闭性. 文[6,7,8]在格半群的意义下研究了格值自动机及其接受的语言的代数性质, 指出了格值正则语言关于交、并、补、闭包、反转、连接、同态、逆同态等代数运算的封闭性成立的条件, 文[17,19]给出了语言或格值语言可以相互epsilon-逼近的概念, 并给出了一些格值正则语言(NLFA)可被确定型格值正则语言(DNLFA) epsilon-逼近的条件.
本文进一步讨论了格值正则语言的代数性质和逼近性质, 首先给出了格值正则语言的商和可容集的概念, 并证明了格值正则语言关于商是封闭的, 格值语言f是格值正则的当且仅当f有一个可容集. 然后我们给出了格值正则语言可被确定型格值正则语言epsilon-逼近的一些充分和必要的条件. 在这些的基础之上, 我们研究了格值正则语言截集的性质, 给出了格值正则语言截集关于代数运算的封闭性成立的一些条件. 例如, 格值正则语言截集的并、交、补在一般的群的意义下是封闭的, 格值正则语言截集和正则语言的并、交、连接仍属于格值正则语言的截集, 格值正则语言截集关于同态、逆同态、商、反转是封闭的, 但关于交和补不一定封闭. 我们还探讨了格值语言或格值正则语言的截集和正则语言的逼近性, 给出了一些充分或必要条件, 并且指出了格值语言的逼近性和其截集的逼近性之间是有一定的联系的, 得到了一些结论. 例如, 当格值正则语言的截集可诱导一个epsilon-覆盖时, 该截集可被一个正则语言epsilon-逼近.