計(jì)算引論5語(yǔ)言與基本概念課件

1、計(jì)算引論第三章 文法與語(yǔ)言第1頁(yè)，共18頁(yè)。第三章 文法與語(yǔ)言3.1 語(yǔ)言的基本概念3.2 有限自動(dòng)機(jī)3.3 上下文無(wú)關(guān)語(yǔ)言3.4 上下文無(wú)關(guān)語(yǔ)言識(shí)別算法第2頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念字母表: 符號(hào)的有限集合。 例如二進(jìn)制字母表0,1字符串: 假定是字符的有限集合，它的每一個(gè)元素稱之為字符。由中字符相連而成的有限序列被稱之為上的字符串（或稱符號(hào)串）。第3頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念空字符串: 不含任何符號(hào)的字符串, 用e表示字符串的長(zhǎng)度即為序列的長(zhǎng)度, 對(duì)字符串, 長(zhǎng)度表示為| |.字母表上的所有字符串, 包括空字符串, 記作*.字符串 *可看成函數(shù) : 1,| (j)的值即

2、為的第j位符號(hào).第4頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念字符串連接: 假定是字符的有限集合, x, y 是上的字符串, 則把y的各個(gè)符號(hào)寫在x的符號(hào)之后得到的字符串稱為x與y的連接, 記作xy或xy,形式地, = x y, 當(dāng)且僅當(dāng)| |=|x|+|y|, (j)=x(j)對(duì)j=1,|x|, 及(|x|+j)=y(j)對(duì)j=1,|y|.例: (1) =a, b, c, x=ab, y=cba, 那么, xy=abcba (2) 01 001= 01001第5頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念設(shè)x是字符串, 把x自身連接n次得到的字符串, 即z=xx x(n個(gè)x), 稱為x的n次方冪, 記作x

3、n。注意：x0= e xn=xxn-1=xn-1x (n1) x*=xn (n0), x+= xn (n1)例如：如果x=a,則x1=a, x2=aa, x3=aaa, 如果x=ab, 則x0= e, x3=ababab第6頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念字符串集合的乘積設(shè)A, B是字符串的集合，則A, B的乘積定義為： AB=x y | xA, yB例如: 設(shè)A=aa, bb, B=cc, dd, ee，則AB=aacc, aadd, aaee, bbcc, bbdd, bbee A2=aaaa, aabb, bbaa, bbbb 第7頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念閉包：如果V是字

4、母表上的字符串集合，那么，V 的閉包定義為：V* = V0V1V2正閉包：V+ = V1 V2 V+ = V* - e例如：V = a, b V* = e, a, b, aa, ab, bb, ba, aaa, V+ = a, b, aa, ab, ba, bb, aaa, 第8頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念字符串v為的子串當(dāng)且僅當(dāng)存在字符串x和y使得 =xvy, 空串e為任何字符串的子串.若對(duì)x有 =xv, 則v是的后綴; 若對(duì)y有 =vy, 則v是的前綴.第9頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念字符串的歸納定義: 對(duì)字符串和自然數(shù) i, 字符串i 可以定義為 0=e, 空串 i+1=

5、 i , 對(duì)每個(gè)i 0字符串的逆, 記作R, 如reverseR=esrever第10頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念有限字母表的任意字符串, 即*的任意一個(gè)子集, 稱為上的一個(gè)語(yǔ)言, 記為: L= *| 具有性質(zhì)P若L1和L2為上的語(yǔ)言, 則它們的連接為L(zhǎng)=L1 L2或L=L1L2, 其中L= *| =x y且xL1及yL2用L*表示所有由L中的字符串及空串連接的字符串集合.第11頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念在計(jì)算理論中的一個(gè)核心問(wèn)題是如何用有限的表示方式來(lái)表示一種語(yǔ)言.例, 令L=w0,1*|其中w中出現(xiàn)23個(gè)1, 第一個(gè)和第二個(gè)不是連續(xù)的, 可用單元素集及符號(hào), 及*表示為

6、0* 1 0* 0 1 0* (10*)*) 簡(jiǎn)寫為L(zhǎng)=0*10*010*(10*)第12頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念正則表達(dá)式：字母表*上的正則表達(dá)式為由(, ), ,*組成的所有字符串, 定義如下： 和的每個(gè)成員都是正則表達(dá)式 如果和為正則表達(dá)式, 則()也是正則表達(dá)式 如果和為正則表達(dá)式,則也是正則表達(dá)式 若為正則表達(dá)式, 則*也是正則表達(dá)式 所有的正則表達(dá)式都是按照14點(diǎn)形成第13頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念語(yǔ)言：若為正則表達(dá)式, 則L()為表示的語(yǔ)言, 其中L為正則表達(dá)式到語(yǔ)言的函數(shù), L定義如下: L()=, L(a)=a其中a若和為正則表達(dá)式, 則L()=L()L

7、()若和為正則表達(dá)式, 則L()=L()L()若為正則表達(dá)式, 則L(*)=L()*每個(gè)正則表達(dá)式都表示一個(gè)語(yǔ)言。第14頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念例,L(ab)*a) =L(a b)*)L(a) (2) =L(a b)*)a (1) =L(a b)*a (4) =(L(a) L(b)*a (3) =(a b)*a (1) =a,b*a =a,b*| 以a結(jié)束第15頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念正規(guī)語(yǔ)言: 由上正則表達(dá)式描述的所有語(yǔ)言都稱為正規(guī)語(yǔ)言, 記作L=L()第16頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念語(yǔ)言識(shí)別器(language recognition device)：識(shí)別字符串是否是語(yǔ)言L的成員的算法。例如, 識(shí)別語(yǔ)言L= 0, 1*| 不含有子串111 識(shí)別：設(shè)置一個(gè)計(jì)數(shù)器, 初值為0, 從左到右依次讀 取被識(shí)別的字符串中每個(gè)字符, 遇到0的時(shí)候計(jì)數(shù)器清0, 遇到1時(shí)計(jì)算器加1, 如果計(jì)數(shù)器為3時(shí)停止, 回答No, 若整個(gè)字符串讀完時(shí)計(jì)數(shù)器不為3, 則回答Yes。第17頁(yè)，共18頁(yè)。3.1 語(yǔ)言的基本概念語(yǔ)言產(chǎn)生器: 說(shuō)明一種語(yǔ)言的如何產(chǎn)生的。例如, 正則式(ebbb)(aababb)* 可認(rèn)