串文法

概念

一般情況下，統計模式識別存在2個問題：

1.有的模式結構很複雜，不能用一個矢量來表示。

2.有的模式識別任務中，我們更關心如何描述它的結構特徵。

因此需要另外一種模式識別：結構模式識別。這其中，句法模式識別主要使用形式語言來描述模式結構，在理論上完備，表1是句法模式識別與統計模式識別的對應關係，下面做介紹。

串文法就是一種機器能識別的語法，所以先講講串文法的語法。

字母表V為字母a,b,c的有限集合。另一方面，句子x,y,z是V中的符號形成的有限長度的字元串。這其中

是V的閉包，包含了字母表能組成所有句子的集合。而

是V的正閉包，就是把閉包裡面的那1個空串去掉。這種區別就像是正數與非負數的關係，非負數去掉0就是非負數了。

串文法

，一個文法或者說語法，有4部分組成就好了。這4個部分依次代表：非終止符、終止符、生成規則、起始符。這其中有

舉個例子：The boy runs.如下圖所示。

非終止符就是那些還要繼續尋找對應關係的元素，比如說Noun，它與我們想表達的Theboy runs.這個句子相比要進一步尋找對應關係，Noun並不是最終出現在句子裡的部分，因此倒了Noun並沒有終止，Noun繼續連結到boy才OK。所以像Noun這樣的元素就叫非終止符。

終止符剛剛介紹了，就是最終要出現在句子裡的部分。像The、boy、runs這些都是。

起始符在這個例子中是Sentence，就是句子開始的標誌。

P（生成規則）比較複雜，生成規則就是符號的變換規則表。就像是法律一樣，在相應的語法環境下，必須按照這個規則來生成句子。

1、無限制文法

這種對文法不加限制，基本沒用。

2、上下文有關文法

這種規則就是說，僅當上下文是

時，中間的非終止符A才能替換成為混串。這就是其名字的由來。

3、上下文無關文法

這種文法是說，不論上下文如何A都可以用

來替換

4、正規文法

正規文法是最常用的一種文法。

四種分類的關係圖：