在前邊的文章中我們把簡單的需要的基礎(chǔ)知識(shí)簡單的列舉了一遍,包括簡單的集合邏輯,還有圖論以及一些的證明方法等等,接下來我們將要開始我們正式的關(guān)于形式語言的學(xué)習(xí),所以這一篇文章,我們將說一下什么是語言,以及語言的一些分類規(guī)則—文法,話不多說,即將開始.

1:什么是語言?

關(guān)于什么是語言這個(gè)問題,大家可能會(huì)想,語言,我們每天說的漢語,英語,甚至我們計(jì)算機(jī)常用的編程語言不都是語言么?在當(dāng)今的世界上,程序設(shè)計(jì)語言可能達(dá)到了幾千種,他們的語言規(guī)則都千差萬別,但是他們總體來看都是有一個(gè)共同的特點(diǎn),都是由一個(gè)有限字母表上的字母的集合所組成的,也就是說我們是可以用一種統(tǒng)一的抽象方法來進(jìn)行討論,研究程序設(shè)計(jì)語言的.形式語言在之前我們提的定義中就是對(duì)程序設(shè)計(jì)語言的形式化描述,這里邊我們就可以引申出兩種重要的方向:

一:研究產(chǎn)生語言的形式規(guī)則—文法

二:識(shí)別語言的裝置—機(jī)器

下邊的這些文字討論的就是這樣的順序和規(guī)則.

在這一篇文章中,我想和大家先了解下有關(guān)語言的術(shù)語,比如說字母表,字符串,語言,以及語言的運(yùn)算規(guī)則等等,然后在此基礎(chǔ)就引申出什么是文法,以及文法的分類等等.(這里邊一些定義類的東西我就直接引用蔣宗禮老師書中的定義,定義類的東西不好自己定義,容易出錯(cuò))

1:字符的有限集合稱為字表,記為T

關(guān)于這條定理,我們可以可以這么理解,比如說26個(gè)英文字母,10個(gè)阿拉伯?dāng)?shù)字都可以構(gòu)成不同的字母表,字母表作為一個(gè)集合,在理論上是可以是一個(gè)無限大的集合的,但是在實(shí)際應(yīng)用上,總會(huì)有一些的規(guī)則,所以字母表的中的字符個(gè)數(shù)總是有限的.

2:由字表T中的字符構(gòu)成的有限序稱為字母表T上的字符(或句子)诊沪。

比如說現(xiàn)在有一個(gè)字母表T={a,b,c,d,.....0,1,2....9},現(xiàn)在隨機(jī)拼出的acab001,bseg9282,這些都可以認(rèn)為是字母表上T的字符串,只是這樣沒有什么意義罷了.

字符串中所包含字符的個(gè)數(shù),稱為字符串的長度。

比如上邊的|acab001| = 7,|bseg9282| = 8,長度為0的字符串,稱為空串,記為ε,空串中是沒有任何字符的字符串,但是這也是有用的.

約定今后小寫字母a,b,c,d表示單個(gè)字符;t,u,v,w,x,y,z表示字符;an表示n個(gè)a的字符匀谣。

3:字符串的運(yùn)算

設(shè)w1和w2是字母表T上的字符,w1=a1a2…am,w2 =b1b2…bn,則w1w2 =a1a2…amb1b2…bn稱為字符w1和w2的連接唉匾。

顯然,字母表上的任意一個(gè)字符w與空串的連接還是w,即εw=wε =w

字符串w的逆,用w表示,w是字符串w的倒置逆粹。如,當(dāng)w=b1b2…bk,則w=bk…b2b1萤晴。空ε的逆還是ε,即ε =ε蔚龙。

設(shè)w1,w2,w3是字母表T上的字符,稱w1是字符w1w2的前綴,w2是w1w2的后綴,且w2是字符串w1w2w3的青柄。

舉個(gè)例子:比如abcd,這樣abc就可以看為是abcd的前綴和子串,d就可以看為abcd的子串和后綴.在這里,子串是一個(gè)特殊情況,他是屬于任何字符串的前綴,后綴,以及子串.

4:T*是字母表T上的所有字符串和空集的集合,T+是字母表T上的所有字符串構(gòu)成的集合,并有T+ =T* - {ε}伐债。

5:字母表T上的語言L是T*的子集.

在這里應(yīng)該注意,?和{ε }是兩個(gè)不同的意思,?表示的是什么也沒有,空句子也不會(huì)存在,{ε }表示的是只有一個(gè)空句子的集合.

比如:設(shè)字母表T是C語言中所用的全部符號(hào)的集合,那么語法正確的C語言程序也是C語言字母表上的語言.

根據(jù)語言的定義可以得到,語言其實(shí)就是一個(gè)集合,因此對(duì)于語言的運(yùn)算就跟集合的運(yùn)算一樣,

并、交刹前、補(bǔ)泳赋、差運(yùn)算均可應(yīng)用于對(duì)語言的運(yùn)算。

6:語言的基本運(yùn)算

1:兩個(gè)語言L1和L2的積L1·L2(簡記為L1L2),是由L1和L2中字符串的連接所構(gòu)成的字符串的集合.

舉例:

設(shè)字母表T={a,b},L1和L2是T上的語言,并有L1={a,b,ab},L2 ={bb,aab}

那么就有:

L1L2 = {abb,aaab,bbb,baab,abbb,abaab}

L2L1 = {bba,bbb,bbab,aaba,aabb,aabab}

上邊的這個(gè)例子也隱藏了一點(diǎn)L1L2≠L2L1,這個(gè)跟矩陣當(dāng)中的積運(yùn)算不可交換是一個(gè)樣子的.

2:語言L的冪可歸納定義如下:

L0 ={ε}

Ln=L·Ln- 1n≥1

接著上邊的例子中的L1,L2,套用上邊的定義:

L21 = {aa,ab,aab,ba,bb,bab,aba,abb,abab}

L22 = {bbbb,bbaab,aabbb,aabaab}

3:語L的閉包L*定義為L* =∪Ln(n≥ 0)

語L的正閉包L+定義為:L+ =∪Ln(n≥ 1)

顯然,L+ =LL* =L*L,L* =L+∪{ε}喇喉。

舉例:

設(shè)L={ba,bb},

則L* ={ba,bb}* = {ε,ba,bb,baba,babb,bbba,bbbb,…}

L+ ={ba,bb}+ = {ba,bb,baba,babb,bbba,bbbb,…}

二:文法

在上文中我們會(huì)發(fā)現(xiàn),如果語言L是有限集合的話,那如果次數(shù)小有限集合的確可以用列舉法來去解決這個(gè)問題,但是如果是無限的集合語言L,那么就不能再用列舉法了,必須要尋找到一個(gè)更加簡便的方法.

科學(xué)家們做了很多的探索:

探索方向1:是所謂“文法”的產(chǎn)生系統(tǒng)祖今。它能夠由定義的文法規(guī)則產(chǎn)生出語言的每個(gè)句子.

探索方向2:是用一個(gè)語言的識(shí)別系統(tǒng)。當(dāng)一個(gè)字符串能夠被一個(gè)語言的識(shí)別系統(tǒng)接受,則說這個(gè)字符串是該語言的一個(gè)句子,否則不屬于該語言.

我們將會(huì)主要討論探索方向1,第二種方法后來演變成了各種語言的識(shí)別器,以后我們可能會(huì)談一談,關(guān)于第一種方法,使用的主要是文法,那什么是文法?

所謂的文法,簡單來說就是一個(gè)定義語言的數(shù)學(xué)模型.蔣老師的書中講的是Chomsky的文法體系,Chomsky文法體系中間的任何一種文法必包含有:兩個(gè)不同的有限符號(hào)集合,即非終結(jié)符號(hào)集合N和終結(jié)符號(hào)集合T;一個(gè)形式化規(guī)則的有限集合P,也稱生成式集合;一個(gè)起始符S。其中,集合P中的生成式是用來產(chǎn)生語言的規(guī)則,則是僅由終結(jié)符組成的字符;同時(shí)這些字符串的產(chǎn)生必須從一個(gè)起始符S開始,不斷使P中的生成式而導(dǎo)出來的千诬∷Ｄ浚可見,文法的核心是生成式集合,它決定了語言中句子的產(chǎn)生。

2:語法的形式定義

1:法G是一個(gè)四元組,G=(N,T,P,S),其中(1)N終結(jié)符的有限集合;

(2)T是終結(jié)符的有限集合,且N∩T=?;

(3)P是形式為α→β的成式有限集合,且a∈(N∪T)+,β∈(N∪T)*,且α少含一個(gè)非終結(jié)符號(hào);

(4)S是起始符,且S∈N徐绑。

PS:在定義,成式α→β中,所用符號(hào)“→”的含義是“可被代替”邪驮。

比如說:設(shè)文法G=(N,T,P,S),其中,N={A,S},T={a},成式P如下:

S→a,S→aA,A→aS.

2:字符α是文法G的句型,當(dāng)且僅當(dāng)S*Gα,且

α∈(N∪T)*;w是G的,當(dāng)且僅當(dāng)S*w,且w∈T*。G

由文法G產(chǎn)生的語(記為L(G))是w|w∈T*且S*w,G

或者說,L(G)中的個(gè)字符,必是由終結(jié)符組成,并且是從起始符S推導(dǎo)出來的傲茄。

舉例:

文法G=({A,S},{a},P,S),其中生成式P如下:S→a,S→aA,A→aS毅访。

這樣的話由文法G產(chǎn)生的語言L(G)有:

Sa a∈L(G),

SaA aaS aaa aaa∈L(G),

SaA aaS aaaA aaaaS aaaaa aaaaa∈L(G),

這樣一直下去

將推導(dǎo)出的語言寫成一般形式,則有

L(G)= {a2n+1}n≥0。

在推導(dǎo)序列S aA aaS aaaA aaaaS aaaaa中,S,aA,aaS,aaaA,aaaaS都是句型,aaaaa則是句子.

3:文法的分類:

1:前面定義的文法,屬于Chomsky的文法體系,該體系對(duì)生成式的形式作一些規(guī)定,分為四類,因此文法也分為四種類型,即0型盘榨、1型喻粹、2型和3型文法,按生成式的不同介紹如下:

1 .0型、1型草巡、2型和3型文法介紹

1型文法:

或者稱為上下文有關(guān)文法守呜。生成式的形式為α→β,其中,|a|<=|β|,并且α,β∈(N∪T)+.

舉例:

設(shè)文法G=(N,T,P,S),其中N= {S,A,B},T= {a,b,c},

那么生成式如下:

S→aSAB,

aA→ab,

S→aAB,

bA→bb,

BA→AB,

bB→bc,

cB→cc

表明G是1型文法,因?yàn)槊總€(gè)生成式左部字符串度小于或等于右部字符串長度。

2型或稱上下文無關(guān)法山憨。生成式的形式為A→α,A∈N且α∈(N∪T)*查乒。

例子:

設(shè)文法G=(N,T,P,S),其中N= {S,B,C},T= {0,1},

生成式P如下:

S→0C,

B→0S,

S→1B,B→1BB,C→ 0CC。

B→0,C→1,

C→ 1S,

在此例子中,每個(gè)生成式的左部是單個(gè)非終結(jié)符,所以是2型文法郁竟。

3型文法或稱正則法玛迄。生成式的形式為A→wB或A→w,A,

B∈N,w∈T*稱右線性文法;如果生成式的形式為A→Bw或A→w,則稱左線性文法。

以上介紹1型枪孩、2型和3型文法,對(duì)這三種類型文法的生成式形式都一些規(guī)定憔晒。如果對(duì)生成式的形式不加任何限制,則定義的文法便是0型文法.

以上定義的1藻肄、2蔑舞、3型文法都是在0型文法的前提下所加的限制,所以必然都屬于0型法。同理,3型文法也屬2型文法,2型文法屬1型文法嘹屯。但要指出,在1型文法中不允許形式為A→ε的生成式存在,所以具有A→ε成式的2型或3型文法不能屬1型文法攻询。

由于文法有四類,所以由這些文法所產(chǎn)生的語言也有四類,即:由上下有關(guān)文法產(chǎn)生的語言稱為上下文有關(guān)語言;由上下無關(guān)文法產(chǎn)生的語言稱為上下文無關(guān)語言;由正則文法產(chǎn)生的語言稱為正則語言;由0型文法產(chǎn)生的語言則稱為無限制性語言。

但是我們?nèi)粘Ｊ褂玫膶ｉT為2型語言文法,我們下一篇將要專門一篇文章講解二型文法.