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

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

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

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