基于量子邏輯的確定型正則文法＊

王擁兵，張麗霞，雷紅軒

（1.安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶246013；2.內(nèi)江師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，四川 內(nèi)江641112）

1 引言

在經(jīng)典計(jì)算機(jī)理論中，自動(dòng)機(jī)和文法都是計(jì)算機(jī)中簡(jiǎn)單而又常見的數(shù)學(xué)模型。它不僅是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)，同時(shí)在匯編語言、編譯語言以及算法設(shè)計(jì)等方面有重要的應(yīng)用［1～5］。文獻(xiàn)［6，7］將自動(dòng)機(jī)狀態(tài)集量子化，進(jìn)一步推廣了經(jīng)典自動(dòng)機(jī)理論，引入了作為量子計(jì)算機(jī)的簡(jiǎn)單模型的量子自動(dòng)機(jī)。由于Shor［8］于1994年發(fā)現(xiàn)了在量子計(jì)算機(jī)上進(jìn)行大數(shù)分解的多項(xiàng)式時(shí)間算法，以及Gover［9］發(fā)現(xiàn)了平方根時(shí)間的量子搜索算法之后，量子計(jì)算日益受到人們的關(guān)注與重視，量子計(jì)算模型便是其中一個(gè)很重要的研究課題。由應(yīng)明生等［10～16］建立的基于量子邏輯的自動(dòng)機(jī)和文法理論是量子計(jì)算模型方面的一個(gè)重要研究方向。特別地，在文獻(xiàn)［12］中給出了基于量子邏輯的自動(dòng)機(jī)對(duì)應(yīng)的Kleene定理表現(xiàn)形式，但量子邏輯意義下的Kleene定理成立要依賴于正交模格中子集的交換子的條件。而文獻(xiàn)［15］從另一個(gè)角度出發(fā)，通過引入廣義的子集構(gòu)造方法，證明了基于量子邏輯的有窮自動(dòng)機(jī)與基于量子邏輯的確定型自動(dòng)機(jī)可以相互轉(zhuǎn)化，進(jìn)而證明了Kleene定理。本文從文法的角度出發(fā)，考慮基于量子邏輯意義下的確定型正則文法，證明了基于量子邏輯的確定型正則文法與基于量子邏輯的確定型自動(dòng)機(jī)是可以相互轉(zhuǎn)化的，并給出了量子確定正則語言的代數(shù)刻畫和層次刻畫以及關(guān)于正則運(yùn)算的封閉性。這些結(jié)果進(jìn)一步豐富了自動(dòng)機(jī)和文法理論。

2 ?－值確定型正則文法

量子邏輯是指真值為完備正交模格?的邏輯，也稱為正交模格值邏輯，見文獻(xiàn)［10～15］。本文采用文獻(xiàn)［15］的有關(guān)記號(hào)。完備的正交模格是七元組?＝ 〈l，≤，∧，∨，⊥，0，1〉，其中：

（1）?＝ 〈l，≤，∧，∨，⊥，0，1〉是完備格，1和0分別是最大元和最小元，≤是偏序，對(duì)X?l，∨X、∧X分別表示X的上確界與下確界。

（2）一元運(yùn)算⊥是?上的正交補(bǔ)，滿足如下條件：?a，b∈l，

①a∧a⊥＝0，a∨a⊥＝1。

②a⊥⊥＝a。

③a≤b蘊(yùn)含b⊥≤a⊥。

很容易看出，條件③與De Morgan對(duì)偶律是等價(jià)的：即 ?a，b∈l，

③′（a∧b）⊥＝a⊥∨b⊥，（a∨b）⊥＝a⊥∧b⊥。

一個(gè)正交模格就是滿足如下正交模律的正交格：?a，b∈l，

④a≤b蘊(yùn)含a∨（a⊥∧b）＝b。

在正交模格?上定義蘊(yùn)含算子→滿足 ?a，b∈l，a→b＝1當(dāng)且僅當(dāng)a≤b。本文假設(shè)→表示Sasaki蘊(yùn)含，即a→b＝a⊥∨（a∧b）。雙蘊(yùn)含的定義為：?a，b∈l，a?b＝（a→b）（b→a）。正交模格值邏輯（即量子邏輯）的語法與經(jīng)典一階邏輯類似。 、∨、→是三個(gè)原始連接詞，?是原始量詞，∧、?是由 、∨、→和?定義的。語義方面，將 、∨、→分別理解為?中的⊥、∨、→運(yùn)算，?解釋為?中的最小上界。集合論公式x∈A的真值為 x∈A ＝A（x）。公式φ是有效的當(dāng)且僅當(dāng) φ ＝1，并記為｜＝?φ。

定義1［15］?－值有窮自動(dòng)機(jī)（簡(jiǎn)記為?-VFA）是五元組 M ＝ （Q，Σ，δ，I，F(xiàn)），其中，Q 為有限狀態(tài)集合；Σ為有限字母表；I，F(xiàn)：Q→l為Q的?－值子集，代表初始狀態(tài)與接受狀態(tài)；δ：Q×Σ×Q→l為?－值轉(zhuǎn)移函數(shù)或量子轉(zhuǎn)移函數(shù)。

以下用σ表示Σ中的符號(hào)，用ω、θ表示Σ中的字符串，ε用來表示空串。為了方便，用?（Σ＊）表示Σ＊上的所有?－值語言之集合。對(duì)?-VFA M＝（Q，Σ，δ，I，F(xiàn)）對(duì)應(yīng)的?－值可識(shí)別謂詞為recM∈?（Σ＊），對(duì)于輸入串ω∈Σ＊，令ω＝σ1σ2…σn，有：

recM（ω）＝ （?q0∈Q）（?q1∈Q）…

（?qn∈Q）（q0∈I∧qn∈F∧

（q0，σ1，q1）∈δ∧ … ∧ （qn－1，σn，qn）∈δ）即命題recM（ω）的真值定義為：

recM（ω） ＝∨ ｛I（q0）∧δ（q0，σ1，q1）∧ … ∧

δ（qn－1，σn，qn）∧F（qn）：q0，…，qn∈Q｝

對(duì)L∈?（Σ＊），若存在?-VFA使得L＝recM，則稱L為Σ＊上的?－值正則語言。

引理1［15，17］設(shè)?為一個(gè)格，X 為?的有限子集，則由X生成的?的∧－半格X∧與∨－半格X∨都是有限的，而且：

X∧＝ ｛x1∧x2∧ … ∧xk：x1，x2，…，xk∈X，k≥1｝∪ ｛1｝

X∨＝ ｛x1∨x2∨ … ∨xk：x1，x2，…，xk∈X，k≥1｝∪ ｛0｝

文獻(xiàn)［15］給出了一種限制了的?-VFA，該定義與文獻(xiàn)［12］定義的確定型?－值自動(dòng)機(jī)有著明顯的不同。

定義2［15］?－值確定型有窮自動(dòng)機(jī)（簡(jiǎn)記為?-VDFA）是五元組 M ＝ （Q，Σ，δ，q0，F(xiàn)），其中，Q為有限狀態(tài)集；Σ為有限字母表；q0∈Q是初始狀態(tài)；F為Q的?－值子集，代表終狀態(tài)；δ：Q×Σ→Q為狀態(tài)轉(zhuǎn)移函數(shù)。

對(duì)?-VDFA M ＝ （Q，Σ，δ，q0，F(xiàn)），對(duì)應(yīng)的?-值可識(shí)別謂詞recM∈?（Σ＊），對(duì)輸入串ω∈Σ＊，令ω＝σ1σ2…σn，

recM（ω）＝ （?q0∈Q）（?q1∈Q）…（?qn∈Q）（qn∈F∧δ（q0，σ1）＝q1∧ … ∧δ（qn－1，σn）＝qn）

則命 題recM的 真 值 定 義 為 recM（ω） ＝F（δ＊（q0，ω））。

引理2［15］對(duì)任意?-VFA M ＝ （Q，Σ，δ，I，F(xiàn)），存在?-VDFA Md＝ （Qd，Σ，η，q0，E）與 M 等價(jià)，即recM＝recMd。

定義3 ?－值正則文法G（簡(jiǎn)記為?-RG）是一個(gè)四元組G＝ （ N，Σ，P，S ） ，其中N為非終止符的非空有限集，Σ是終止符的非空有限集，且N∩Σ＝?，而I：N→l，即N的?－值子集（量子開始符號(hào)）。命題“S為開始記號(hào)”，記為S∈I，真值為I（S），P＝ ｛ A →ρx：A∈N，x∈ΣB，B∈N ∪｛Λ｝或A ＝ S，x＝Λ，ρ∈l－ ｛0｝｝，且P 的 支集Supp（P）有限，表示?－值產(chǎn)生式的有限集合，其中A→ρx被解釋為變?cè)狝可被替換為任意字符串x的真值為ρ，即 A→x ＝ρ。

則命題derG（ω）的真值定義為：

此時(shí)，derG稱為?－值正則文法G生成Σ＊上的?－值正則語言。同樣地，對(duì)任意L∈?（Σ＊），若存在?-RG G使得L＝derG，則稱L為Σ＊上的?－值正則語言（或稱量子正則語言）。

對(duì)任一?-RG G＝ （ N，Σ，P，I） ，G生成的量子正則語言derG作為Σ＊到l的函數(shù)，其像集：Im （de rG） ＝ ｛ r∈l：?ω ∈Σ＊，derG（ω） ＝r｝是derG（ω）的有限子集。

由上述討論可知，對(duì)任一?-RG來說，它產(chǎn)生的語言的像集總是有限的，所以在討論?-RG的過程中，雖然格?可能是無限的，但對(duì)于?-RG G來說，它產(chǎn)生的語言的真值只取?中的有限子集，因此總可以假設(shè)?為有限的正交模格，從而可以簡(jiǎn)化討論。而對(duì)于?為無限的正交模格的情形，以下討論都是成立的。

在基于量子邏輯的自動(dòng)機(jī)理論中，很多重要的定理成立都必須依賴于正交模格中子集的交換子的條件來保證，特別地，在量子邏輯的情況下，?－值正則語言對(duì)于語言的交、補(bǔ)、Kleene閉包運(yùn)算并不封閉，所以文獻(xiàn)［12］給出了一些條件，包括交換子分配律的條件，來保證這些運(yùn)算的封閉性。文獻(xiàn)［15］定義了?－值有窮自動(dòng)機(jī)（?-VFA）和?－值確定型有窮自動(dòng)機(jī)（?-VDFA），并通過廣義子集構(gòu)造，證明了它們是等價(jià)的。?-VFA與?-VDFA等價(jià)性還表明量子邏輯下的有窮自動(dòng)機(jī)可以處理量子語言，但它們?cè)谔幚淼倪^程中直接使用經(jīng)典有窮自動(dòng)機(jī)的相關(guān)技術(shù)。需要注意的是，?-VFA轉(zhuǎn)化?-VDFA，復(fù)雜性會(huì)增加，但對(duì)于?－值正則語言對(duì)于語言的交、補(bǔ)、Kleene閉包封閉性的討論帶來了極大方便。

定義6 ?－值確定型正則文法（簡(jiǎn)記為?-DRG）是一個(gè)四元組G＝ （N，Σ，P，I），其中N 為有限非終止符集；Σ為有限終止符集；I為N的?－值子集，代表開始符號(hào)；而這里的?－值產(chǎn)生式P為如下形式：

其中A、B∈N，u∈Σ，ρ∈l－｛0｝。顯然，?-DRG是一種特殊的?-RG。

對(duì)?-DRG G＝ （N，Σ，P，I），定義在Σ＊上的一元?－值可產(chǎn)生的謂詞dderG，對(duì)于任意ω∈Σ＊，有：

則命題dderG（ω）的真值定義為：

對(duì)任意L ∈?（Σ＊），若存在?-DRG G 使得L＝dderG，則稱L為Σ＊上的量子確定正則語言（?－值確定正則語言）。

定理1 設(shè)G＝ （N，Σ，P，I）為任一?-DRG，則存在?-VDFA M使得對(duì)任意ω∈Σ＊，有：

即recM＝dderG。

其中ρZk為某個(gè)狀態(tài)Zk所對(duì)應(yīng)的產(chǎn)生式的真值。

而對(duì)ω ≠Λ，令ω ＝u1u2…un－1un，則存在S∈I，使得在?-DRG G中的推導(dǎo)鏈為：

1.2.1 對(duì)照組 常規(guī)護(hù)理，包括術(shù)前訪視、術(shù)前準(zhǔn)備、入室的安撫、麻醉護(hù)理、體位管理、醫(yī)護(hù)配合，對(duì)于沖洗液需要控制好溫度。術(shù)中密切監(jiān)測(cè)患者的生命體征，出現(xiàn)異常，遵醫(yī)囑給予靜脈用藥等干預(yù)，糾正呼吸循環(huán)紊亂。出現(xiàn)術(shù)中出血等并發(fā)癥，配合醫(yī)師做好救治。糖尿病對(duì)象，需要在術(shù)前確認(rèn)血糖控制情況，胰島素控制血糖的療效。血糖達(dá)標(biāo)的對(duì)象常規(guī)口服二甲雙胍和（或）阿卡波糖控制血糖，高血糖（＞8.3 mmol/L)的對(duì)象給予胰島素控制血糖，低血糖（＜5.1 mmol/L）輸液糾正，將血糖控制在5.6～11.2 mmol/L。

定理 2 設(shè) M ＝ （Q，Σ，δ，x0，F(xiàn)）為 任 一?-VDFA，則存在?-DRG G使得對(duì)任意ω ∈Σ＊，有：

證明 設(shè) M ＝ （Q，Σ，δ，x0，F(xiàn)）為一?-VDFA，現(xiàn)構(gòu)造一個(gè)?-DRGG＝ （N，Σ，P，I）如下：

根據(jù)上述兩個(gè)結(jié)論，我們得到下面的結(jié)論：

定理3 對(duì)有限集Σ上的量子語言L，L被一個(gè)?-DRGG產(chǎn)生當(dāng)且僅當(dāng)L被一個(gè)?-VDFA M識(shí)別。

根據(jù)上述討論，?-DRG產(chǎn)生的?－值確定正則語言與?-VDFA識(shí)別的量子語言等價(jià)，進(jìn)一步可以證明?-RG 與?-VFA 是等價(jià)的，而?-VFA 又與?-VDFA是等價(jià)，并根據(jù)引理1，可以驗(yàn)證基于量子邏輯的確定型正則文法和量子正則文法是等價(jià)的。

定理4 設(shè)?為一完備正交模格，X為?的任意有限子集，如果由X生成的子代數(shù)是有限集，則對(duì)任意?-RGG，都存在一個(gè)與其等價(jià)的?-DRG G′，即dderG′＝derG。

3 ?－值確定型正則文法的性質(zhì)

引理2 設(shè)量子文法G1＝ （N，Σ，P，I），I為N 的?－值子集，代表開始符號(hào)，而這里的?－值產(chǎn)生式P只有形式為A→1uB ，其中B∈N∪｛Λ｝，u∈Σ，其產(chǎn)生的量子語言定義為：

這類?－值量子文法與?-DRG是等價(jià)的。

定理5 設(shè)L：Σ＊→l為?－值量子語言，以下條件等價(jià)：

（1）存在?-DRG G，使得L＝dderG；

（2）存在k1，k2，…，kn∈ l－｛0｝，及正則語言L1，L2，…，Ln使得L＝∨in＝1ki1Li，其中1Li表示Li的特征函數(shù)；

（3）存在k1，k2，…，kn∈ l－｛0｝，及兩兩不交的正則語言L1，L2，…，Ln使得L ＝ ∨in＝1ki1Li。

證 明 （ 1）?（3）：設(shè) L 由 ? -DRG G ＝（N，Σ，P，I） 產(chǎn)生，則對(duì)任意ω∈Σ＊，根據(jù)引理2，存在與之等價(jià)量子文法G1＝ （ N1，Σ，P1，I1），并且有 derG1（ω） ＝ ∨S∈I1｛I1（S）S?＊ω｝。設(shè)Im（I1） － ｛0｝＝ ｛k1，k2，…，kn｝ ，令 I（i）＝｛S ∈ N1：I1（S）＝ki｝ ，由 此 構(gòu) 造 的 文 法 G（i）＝（N，Σ，P（i），I（i）） 為經(jīng)典的文法，其中P（i）為P1去真值所對(duì)應(yīng)的經(jīng)典產(chǎn)生式的集合。設(shè)該文法產(chǎn)生的語言為L(zhǎng)i，根據(jù)構(gòu)造知，Li為正則語言且｛Li｝in是兩兩不相交的。

因此，ω∈Li當(dāng)且僅當(dāng)S?＊ω且S∈I（i），由此可知，

（3）?（2）：顯然。

（2）?（1）： 設(shè) Li被 正 則 文 法 Gi＝（Ni，Σ，Pi，Si） 產(chǎn)生，且當(dāng)i≠j時(shí)，Ni∩Nj＝?，i，j∈ ｛ 1，2，…，n｝。構(gòu)造文法G＝ （ N，Σ，P，I）如下：N＝∪in＝1Ni，對(duì)于Pi中的產(chǎn)生式A→uB或者S0i→Λ∈Pi，其中B∈N∪｛Λ｝，便將這些產(chǎn)生式賦真值為1放入P 中，并令I(lǐng)（A）＝由引理2，存在與之等價(jià)的?-DRG G′，使得derG′

定理6 設(shè)L：Σ＊→l為量子語言，以下命題等價(jià)：

（1）存在?-DRG G，使得L＝dderG。

（2）集合Im（L）為有限集，且對(duì)任意的k∈l－｛｝0，L的r-層集，L［k］＝｛ω∈Σ＊：L（ω）＝k｝是Σ 上的正則語言，且 L ＝dderG＝ ∨k∈l－｛0｝k1L［k］，其中1L［k］表示L［k］的特征函數(shù)。

（3）集合Im（L）為有限集，且 ?a∈l－｛0｝，A［a］為正則語言。

關(guān)于?－值語言的運(yùn)算如下：對(duì)任意A，B∈?（Σ＊）以及r∈l，并A∨B，交A∧B，補(bǔ)A⊥，數(shù)量積rA，連接AB，Kleene閉包A＊定義為，對(duì)任意ω∈Σ＊，

A∨B（ω）＝A（ω）∨B（ω）；

A∧B（ω）＝A（ω）∧B（ω）；

A⊥（ω）＝A（ω）⊥；

rA（ω）＝r∧A（ω）；

AB（ω）＝∨ ｛A（ω1）∧B（ω2）：ω1ω2＝ω｝；

A＊（ω）＝∨ ｛A（ω1）∧ … ∧A（ωn）：n≥1，ω1…ωn＝ω｝。

定理7 ?－值確定正則語言關(guān)于?－值語言的有限并、有限交、數(shù)量積、補(bǔ)運(yùn)算、連接運(yùn)算、Kleene閉包運(yùn)算封閉。

定理8 設(shè)f：Σ＊1→Σ＊2為同態(tài)映射，若L為?－值確定正則語言，則f－1（L）也是?－值確定正則語言。

說明：定理7與定理8的證明類似于文獻(xiàn)［15］的證明。

4 結(jié)束語

本文利用語義分析方法進(jìn)一步研究了基于量子邏輯的確定型正則文法理論，證明了量子邏輯意義下的確定型正則文法與確定型有窮自動(dòng)機(jī)的等價(jià)，討論了量子邏輯意義下的正則文法可以通過經(jīng)典正則文法與量子開始符號(hào)來實(shí)現(xiàn)，這對(duì)討論量子邏輯下的文法帶來了方便，從復(fù)雜性角度來分析，也是易行的。

［1］ Hopcroft J E，Ullman J D.Introduction to automata theory，languages and computation［M］.New York：Addison-Wesley，1979.

［2］ Zadeh L A.Outline of a new approach to the analysis of complex systems and decision processes［J］.IEEE Transactions on Systems，Man，and Cybernetics，1973（1）：28-44.

［3］ Mordeson J N，Malik D S.Fuzzy and languages：Theory and applications［M］.London：Chapman ＆Hall／CRC，2002.

［4］ Sheng L，Li Y M.Regular grammars with truth values in lattice-monoid and their languages［J］.Soft Computing，2006（10）：79-86.

［5］ Chen Bing，Zhou Zu-de，Chen You-ping，el al.Schedulability analysis of the CAN network using timed automata［J］.Computer Engineering ＆ Science，2006，28（9）：25-27.（in Chinese）

［6］ Moore C，Crutchfield J P.Quantum automata and quantum grammars［J］.Theoretical Computer Science，2000，237（1-2）：275-306.

［7］ Gudder S.Basic properties of quantum automata［J］.Foundation of Physics，2000，30（2）：301-319.

［8］ Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer［J］.SIAM Journal on Computing，1997，26（5）：1484-1509.

［9］ Grover L K.Quantum mechanics helps in searching for a needle in a haystack［J］.Physical Review Letters，1997，79（2）：325-328.

［10］ Ying M S.Automata theory based on quantum logic（I）［J］.International Journal of Theoretical Physics，2000，39（4）：891-991.

［11］ Ying M S.Automata theory based on quantum logic（II）

［J］.International Journal of Theoretical Physics，2000，39（11）：2545-2557.

［12］ Ying M S.A theory of computation based on quantum logic（I）［J］.Theoretical Computer Science，2005，344：134-207.

［13］ Qiu D W.Automata theory based on quantum logic：Some characterizations［J］.Information and Computation，2004，190：179-195.

［14］ Qiu Dao-wen.Automata and grammars theory based on quantum logic［J］.Journal of Software，2003，14（1）：23-27.（in Chinese）

［15］ Li Yong-ming.Finite automata based on quantum logic and monadic second-order quantum logic［J］.Science in China Series F：Information Sciences，2010，53（1）：101-114.

［16］ Han Zhao-wei，Li Yong-ming.Pushdown automata and context-free grammars based on quantum logic［J］.Journal of Software，2010，21（9）：2107-2117.（in Chinese）

［17］ Li Y M.Free semilattices and strongly free semilattices generated by partially ordered sets［J］.Northeastern Mathematical Journal，1993，9（3）：359-366.

附中文參考文獻(xiàn)：

［5］ 陳冰，周祖德，陳幼平，等.基于時(shí)間自動(dòng)機(jī)的CAN網(wǎng)絡(luò)可調(diào)度性分析［J］.計(jì)算機(jī)工程與科學(xué)，2006，28（9）：25-27.

［14］ 邱道文.基于量子邏輯的自動(dòng)機(jī)和文法理論［J］.軟件學(xué)報(bào)，2003，14（1）：23-27.

［16］ 韓召偉，李永明.基于量子邏輯的下推自動(dòng)機(jī)與上下文無關(guān)文法［J］.軟件學(xué)報(bào)，2010，21（9）：2107-2117.