計算引論5語言與基本概念課件

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

2、為的第j位符號.第4頁，共18頁。3.1 語言的基本概念字符串連接: 假定是字符的有限集合, x, y 是上的字符串, 則把y的各個符號寫在x的符號之后得到的字符串稱為x與y的連接, 記作xy或xy,形式地, = x y, 當且僅當| |=|x|+|y|, (j)=x(j)對j=1,|x|, 及(|x|+j)=y(j)對j=1,|y|.例: (1) =a, b, c, x=ab, y=cba, 那么, xy=abcba (2) 01 001= 01001第5頁，共18頁。3.1 語言的基本概念設(shè)x是字符串, 把x自身連接n次得到的字符串, 即z=xx x(n個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頁，共18頁。3.1 語言的基本概念字符串集合的乘積設(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頁，共18頁。3.1 語言的基本概念閉包：如果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頁，共18頁。3.1 語言的基本概念字符串v為的子串當且僅當存在字符串x和y使得 =xvy, 空串e為任何字符串的子串.若對x有 =xv, 則v是的后綴; 若對y有 =vy, 則v是的前綴.第9頁，共18頁。3.1 語言的基本概念字符串的歸納定義: 對字符串和自然數(shù) i, 字符串i 可以定義為 0=e, 空串 i+1=

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

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

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