正規(guī)的語法特點

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

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

舉個樣例

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

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

?

自嵌入特性

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

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

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

?

?

什么是自嵌入特性？

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

當然必須保證v和x不能是空串。

?

uvwxy定理

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

就是說，當這個文法滿足自嵌入條件，表示出來就是

那么，能夠得到

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

就是必需要用真正的上下文無關文法。

?

以下介紹上下文無關文法的等價文法。

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

?

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

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

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

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

?

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

細分又有2類。

通俗說

1.無尾的無用非終止符

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

有頭無尾。

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

不存在x使得

?

2.無頭的無用非終止符

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

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

從起始符S開始，不存在

?

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

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

其一消去。

其二修正。

?

消去過程

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

就是要求出全部非終止符各自相應能到達的全部非終止符集合。

?

舉個樣例就好了

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

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

記

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

記

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

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

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

?

于是這相應的3個集合就求完了

?

修正過程

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

圖1

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

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

?

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

那么就得補上S到BAb。綠線代表。

?

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

?

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

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

?

消去無尾非終止符

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

方法是

這個表達式非常清晰。還是舉個樣例。反而繞口。但還是舉吧

這個表達式事實上是一步步找到那些終于的到達終止符的非終止符。

首先J0(G)為空集。

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

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

好繞口。。。

事實上就是{S,A}

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

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

?

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

?

再說說消去無頭非終止符

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

用表達式表示是這種

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

?

還是舉個樣例

展開起始符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是無頭的非終止符，趕緊刪掉與它有關系的全部表達關系就好了。不再贅述。

?

上下文無關文法的2中標準型

1.C（Chomsky）標準型

舉一個樣例馬上就知道怎么把隨便一個上下文無關文本變成C標準型了：

?

2.G（Greibach）標準型

這個嚴格的轉(zhuǎn)化方法有點畸形，就臨時不展開了。

簡單情況用湊的就好了。

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

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

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

轉(zhuǎn)載于:https://www.cnblogs.com/blfshiye/p/4621922.html

總結

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

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