正規(guī)的語法特點(diǎn)

1.全部長(zhǎng)度有限的語言都是正規(guī)的。

2.用正規(guī)文法當(dāng)然能產(chǎn)生無限長(zhǎng)串，當(dāng)中周期反復(fù)部分的長(zhǎng)度不大于非終止符的長(zhǎng)度。

舉個(gè)樣例

<img src="http://latex.codecogs.com/gif.latex?

S o aA,A o bS,A o c" alt="">

在此規(guī)則之下。能生成句子

當(dāng)中周期反復(fù)部分為ab，這個(gè)樣例的非終止符的元素個(gè)數(shù)為2，故滿足2不大于2.

自嵌入特性

我們把上下文無關(guān)文法中的正規(guī)文法去掉。剩下的那部分我們叫做真正的上下文無關(guān)文法。

自嵌入特性是區(qū)分真正的上下文無關(guān)文法與正規(guī)文法的判定標(biāo)準(zhǔn)。

即一個(gè)真正的上下文無關(guān)文法一定具有自嵌入特性。正規(guī)文法具有非自嵌入特性。亦即非自嵌入的上下文無關(guān)文法是正規(guī)文法。上下文無關(guān)文法就蛻化了。

什么是自嵌入特性？

自嵌入顧名思義，就是可以自己嵌入自己：

當(dāng)然必須保證v和x不能是空串。

uvwxy定理

這是一個(gè)用以判定上下文無關(guān)文法和正規(guī)文法的條件。

就是說，當(dāng)這個(gè)文法滿足自嵌入條件，表示出來就是

<img src="http://latex.codecogs.com/gif.latex?

Smathop Rightarrow limits_G^* uAy,Amathop Rightarrow limits_G^* vAx,Amathop Rightarrow limits_G^* w" alt="">

那么，能夠得到

當(dāng)中當(dāng)v和x的反復(fù)次數(shù)同樣且為非空串時(shí)，則這個(gè)文法肯定就是真正的上下文無關(guān)文法。由于這樣的周期形式是正規(guī)文法所不具有的。比方這樣的

<img src="http://latex.codecogs.com/gif.latex?

c{a^i}d{b^i}" alt="">

就是必需要用真正的上下文無關(guān)文法。

以下介紹上下文無關(guān)文法的等價(jià)文法。

不同的上下文無關(guān)文法。它們生成的語言有可能是等價(jià)的，這樣就涉及到一個(gè)最優(yōu)文法的問題。那么最優(yōu)是什么？最有就是高效、沒有冗余和浪費(fèi)。

粗略說有2種冗余，并且僅僅有非終止符可以冗余。終止符總是實(shí)用的啦。

其一是浪費(fèi)環(huán)節(jié)。

浪費(fèi)環(huán)節(jié)是說由單個(gè)非終止符傳遞到了單個(gè)的非終止符。比方

這樣的形式意味著B是多此一舉的。還不如直接A到C呢。

其二是無用環(huán)節(jié)。

細(xì)分又有2類。

通俗說

1.無尾的無用非終止符

所謂無尾，就是咱用了這個(gè)終止符，話根本都沒法結(jié)束。

有頭無尾。

A根本沒法最后變成常量（終止符）。

不存在x使得

2.無頭的無用非終止符

所謂無頭，就是這句話根本就不可能從這個(gè)非終止符開始。有尾無頭。

從起始符開始根本找不到含有A的句子。

從起始符S開始，不存在

首先介紹怎樣消去浪費(fèi)環(huán)節(jié)。

消去浪費(fèi)環(huán)節(jié)包含2個(gè)部分。

其一消去。

其二修正。

消去過程

這個(gè)過程用遞歸算法來實(shí)現(xiàn)。

就是要求出全部非終止符各自相應(yīng)能到達(dá)的全部非終止符集合。

舉個(gè)樣例就好了

<img src="http://latex.codecogs.com/gif.latex?

{G_1}= left( {left{ {S,A,B} ight},left{ {a,b} ight},P,S} ight)" alt="">

如今消去浪費(fèi)環(huán)節(jié)，先考慮S。

發(fā)現(xiàn)S能在一步之內(nèi)的非終止符僅僅有A

記

在K1(S)集合中再次出發(fā)。在一步之內(nèi)能走到的新非終止符僅僅有B

記<img src="http://latex.codecogs.com/gif.latex?

{K_2}(S)= left{ {S,A} ight} cup left{ B ight} = left{ {S,A,B} ight}" alt="">

再往后沒有新的非終止符了。

同理考察A，A在一步之內(nèi)能到達(dá)的非終止符僅僅有B了，記

再考察B，B根本就沒有能在一步之內(nèi)能到達(dá)的新終止符。

于是這相應(yīng)的3個(gè)集合就求完了

修正過程

修正過程就依照上面的消去過程打補(bǔ)丁就好了，由于要消去一堆連接。舊橋拆了總得又一次修吧。還是上面那個(gè)樣例，先把之前的生成關(guān)系畫出來，如圖1黑線所看到的。

<img src="http://img.blog.csdn.net/20140517234450937?

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveWNoZW5nX3NqdHU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">

圖1

如今考慮A，依據(jù)集合，我們要去掉A到B的連接

那么就得補(bǔ)上S到b、A到b、S到aS、A到aS。黃線代表。

然后再考慮S。要去掉S到A

那么就得補(bǔ)上S到BAb。綠線代表。

注意：如今盡管看起來文法規(guī)則比曾經(jīng)更麻煩了，可是，實(shí)際生成句子的過程卻變得簡(jiǎn)單了很多，所以簡(jiǎn)化沒簡(jiǎn)化還是要看療效。

以下介紹消去沒用的終止符

消去無用終止符的思路就是。找出全部實(shí)用的非終止符，那么剩下的自然就是沒實(shí)用的了。

消去無尾非終止符

找出全部的有尾非終止符集合。定義為J(G)

方法是

<img src="http://latex.codecogs.com/gif.latex?

egin{array}{l}{J_0}(G)= phi \{J_{i+ 1}}(G) = {J_i}left( G ight) cup left{ {A|A in {V_N},A o alpha,alpha in {{left( {{V_T} cup{J_{m{i}}}left( G ight)} ight)}^*}} ight}end{array}" alt="">

這個(gè)表達(dá)式非常清晰。還是舉個(gè)樣例。反而繞口。但還是舉吧

這個(gè)表達(dá)式事實(shí)上是一步步找到那些終于的到達(dá)終止符的非終止符。

首先J0(G)為空集。

則J1(G)為全部能一步走到以終止符為尾的非終止符，即A

繼續(xù)，J2(G)是J1(G)并上全部能在一步之內(nèi)到以J1(G)或者其它終止符為尾的非終止符。

好繞口。。。

事實(shí)上就是{S,A}

再往下就找不到了。只是如今忽然發(fā)現(xiàn)，B呢？怎么沒看到B的影子。

這就說明B就是無尾的無用非終止符。

去掉全部跟B有過關(guān)系的生成關(guān)系就好。如今是新的生成關(guān)系

<img src="http://latex.codecogs.com/gif.latex?

egin{array}{*{20}{l}}{S o bA}\{A o aA}\{A o b}end{array}" alt="">

再說說消去無頭非終止符

也是僅僅要找出全部有頭的非終止符就好。剩下自然就無頭了

用表達(dá)式表示是這種

這個(gè)表達(dá)式的意義事實(shí)上就是從起始符，回溯一步步展開，希望能找到句子的頭部。

還是舉個(gè)樣例

展開起始符S，發(fā)現(xiàn)S能到aAA，因此R1(S)={S,A}

A繼續(xù)展開。發(fā)現(xiàn)A能到aCA。因此R2(S)={S,A,C}

搞定，又發(fā)現(xiàn)原來B是無頭的非終止符，趕緊刪掉與它有關(guān)系的全部表達(dá)關(guān)系就好了。不再贅述。

上下文無關(guān)文法的2中標(biāo)準(zhǔn)型

1.C（Chomsky）標(biāo)準(zhǔn)型

舉一個(gè)樣例馬上就知道怎么把隨便一個(gè)上下文無關(guān)文本變成C標(biāo)準(zhǔn)型了：

2.G（Greibach）標(biāo)準(zhǔn)型

<img src="http://latex.codecogs.com/gif.latex?

egin{array}{l}A o aalpha left( {alpha in V_N^*}ight)\A o aend{array}" alt="">

這個(gè)嚴(yán)格的轉(zhuǎn)化方法有點(diǎn)畸形，就臨時(shí)不展開了。

簡(jiǎn)單情況用湊的就好了。

歡迎參與討論并關(guān)注本博客和微博以及知乎個(gè)人主頁，興許內(nèi)容繼續(xù)更新哦~

轉(zhuǎn)載請(qǐng)您尊重作者的勞動(dòng)，完整保留上述文字以及本文鏈接，感謝您的支持！

版權(quán)聲明：本文博客原創(chuàng)文章，博客，未經(jīng)同意，不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的句法模式识别（两）-正规文法、上下文无关文法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。