· Chap 5 Context-Free Languages
- Assignment 1 [ pdf ]
- - -
Ch4.2
Ch4.3
- The pumping lemma: 在一個有m個state的automata裡, 走m步一定有重複的states(by pigeonhole) -> 我們用這個lemma去證明一個語言不是正規
證明方法通常先取一個長度大於m的例子(這樣等下才能套用lemma), 將這個例子拆成xyz三部分, 其中|xy|<m, 根據 pumping lemma, y是一個cycle, 應該要取幾次方都可以, 所以我們就取y的0~無窮次得到w0, w1, w2,...., 接下來只要證明這其中的某一個w不屬於L(格式不合)就可以
所以最tricky的地方是一開始取的例子,
取例子沒有一定的方法, 所以最好能多做題目,
取例子的原則, 是要取一個"很容易打破規則"的例子
- 非正規語言有以下特性:
(1)無法寫成正規表示式 ,
像 a^nb^n這種不是rex, 正規表示式的指數部分必須是已知的常數或*
(2)仍然可以用automata表示, 只是絕對是nfa, 不是dfa
如果是dfa, 那就是regular了
(3)最好也最常用的表示法是Grammar,
其Grammar不像regular只限定either right-linear or left-linear(只能二選一)
非正規語言可以允許right-linear和left-linear混雜, 簡稱linear
(4)絕對是infinite
如果是finite, 就可以用dfa表示, 那就是regular了
- - -
Ch5.1
context free, 是範圍更大.更不嚴謹的語言, 例: {a^nb^n}
之前介紹的都是regular, 包含於context free之中
- - -
期中考取消 @@"
作業也不用交
到學期末大概會一試定生死
怎麼會那麼刺激XD
沒有留言:
張貼留言