非經(jīng)典自動機與形式語言理論研究.pdf

1、本文主要研究非經(jīng)典自動機和形式語言理論中的幾個基本問題。具體研究內(nèi)容如下： 在第二章中，我們對量子計算理論方面的研究進展作了一個全面的介紹。就我們所知，這是現(xiàn)有文獻中第一篇關(guān)于量子計算理論的綜述性文章。 經(jīng)典自動機理論和經(jīng)典形式文法理論之間有密切的關(guān)系。受啟于此，在第三章中，從應(yīng)明生教授提出的基于量子邏輯的自動機理論出發(fā)，我們建立了基于量子邏輯的文法理論的一般框架，并且證明了l-值量子正規(guī)文法生成的l-值量子正規(guī)語言類和

2、l-值量子自動機識別的l-值量子語言類是一致的。為了研究量子計算，Moore和Crutchfield提出了量子有限狀態(tài)自動機、量子下推自動機、量子正規(guī)文法以及量子上下文無關(guān)文法的概念。在第四章里，我們證明了正規(guī)量子文法生成的語言與正規(guī)文法生成的語言是等價的。因此，從生成語言的角度看，正規(guī)量子文法并不比經(jīng)典正規(guī)文法強。這意味著可能需要更合適地定義量子文法甚至量子自動機。 在第五章中，我們介紹了一種新的模糊有限狀態(tài)自動機。對應(yīng)于經(jīng)典

3、的Mealy型有限狀態(tài)自動機，稱之為新Mealy型模糊有限狀態(tài)自動機。從引入的兩類狀態(tài)等價關(guān)系出發(fā)，我們定義了該自動機的最小化形式，最后得到了該自動機的一種狀態(tài)最小化約簡算法。 在第六章中，我們研究了Mizumoto型模糊有限自動機的狀態(tài)最小化約簡算法。與第五章中的方法類似，我們也首先引入了兩種狀態(tài)等價關(guān)系，然后根據(jù)這兩種等價關(guān)系定義了該模糊有限自動機的狀態(tài)最小化形式，并且給出了一個狀態(tài)最小化約簡算法。 在現(xiàn)有的文獻中，