一、基本概念

1.字符串：假定 Σ 是字符的有限集合，它的每一個元素稱之為字符。由 Σ 中字符相連而成的有限序列被稱之為Σ上的字符串。

這是教材對于字符串的定義，通俗地理解，字符串就是一連串的字符。不包括任何字符的字符串稱為空串，記作 ε。

包括空串的 Σ 上字符串的全體記為 Σ*。例如Σ=abcd。 Σ*可以理解為a、b、c、d這四個字符的任意組合再加上空串ε的集合。

2.字符串的連接：例如 x=abc，y=def。x和y連接記作xy=abcdef。x和x自身連接，記作x的平方，同理n個x連接記作x的n次方

3.字符串集合的乘積：設(shè)A, B是符號串的集合，則A, B的乘積定義為：AB = {xy | x ∈ A, y ∈ B}。

? ?例如?設(shè)A={aa, bb}, B={cc, dd, ee}，則 AB={aacc, aadd, aaee, bbcc, bbdd, bbee}

4.字符串集合的閉包：如果V是字符表Σ上的字符串集合，那么V 的閉包定義為：V* = V0 ∪ V1∪ V2 ∪ …

例如：V = {a, b}

V0 = {ε}，V1 = {a，b}，V2 = {aa，ab，ba，bb}，V3={aaa，aab，...}

V* = {ε, a, b, aa, ab, bb, ba, aaa, … }

V+ = {a, b, aa, ab, ba, bb, aaa, …}

值得注意的是閉包是有無窮個元素的。

二、文法（形式語言

）

以上是一些關(guān)于字符串的概念以及操作。接下來就可以引出形式語言的定義。

形式語法是一個4元組 G=(N, Σ, P, S)。其中 N 是非終結(jié)符的有限集合(有時也叫變量集或句法種類集)；Σ 是終結(jié)符的有限集合，N ∩ Σ = Φ；V = N ∪ Σ 稱總詞匯表；P 是一組重寫規(guī)則的有限集合：P={ α→β }， 其中，α，β 是 V 中元素構(gòu)成的串，但 α 中至少應(yīng)含 有一個非終結(jié)符號；S ∈ N，稱為句子符或初始符。

這是教材的定義，比較抽象，理解起來也比較困難。用具體形象的例子來幫助理解可能更好。

N是非終結(jié)符，N可以理解成像人類、動物、植物這種抽象且包含范圍廣的詞。Σ是終結(jié)符，可以理解成比較具體的詞，例如：男老師，女記者，獅子，梅花等。

P是產(chǎn)生式，可以理解成規(guī)則，這個規(guī)則決定了產(chǎn)生的句子。例如人類男老師，人類女記者，人類獅子等等，以上這些都是產(chǎn)生式。什么樣的規(guī)則產(chǎn)生什么樣的句子。

S是開始符，開始符就是第一個非終止符，上述例子中的開始符就是“人類”。

接下來舉一個文法的例子：G = ({A, S}, {0, 1}, P, S) 其中P: S → 0A10，A → 00A1，A → 1

那么，S0A10，S000A110，S0001110。通過這三步，就可以得到這個符合這個文法的一個句子“0001110”

這就可以引出語言的概念：

文法 G 的不含非終結(jié)符的句子形式稱為 G 生成的句子。由文法 G 生成的語言，記作 L(G)，指 G 生成 的所有句子的集合。即：L(G) = {x | x ∈ Σ, S?x }。x是根據(jù)文法G推導(dǎo)出來的，w稱為文法G產(chǎn)生的一個句子。

這就是有關(guān)文法的一些基本概念知識，教材中有一些已知句子，求出句子的文法的題，這些問題沒有特別的求解套路，不是太容易想到。因此，這部分的只看了看例子。下部分開始學(xué)習(xí)喬姆斯基4型文法。

參考資料有：宗成慶的《統(tǒng)計自然語言處理》

總結(jié)

以上是生活随笔為你收集整理的自然语言处理（一）——文法（形式语言）基本概念的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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