Final 日期

Pervasive Computing, 1/2放假, 所以應該是 1/9

1. Apriori

2. Prefix-Span

3. Decision Tree

4. Session06_SpatialData.pdf (pages 104~130)

5. Session07_MobileSpatial.pdf (all)

Formal Language, 1/12
全範圍

Algorithm, 1/11
全範圍

2016/12/15 Formal Language

• 有一個Assignment 2 , 老師說上課會講解, 不知道要不要交? 目前沒說要交
• 複習ch11
• 上ch12

-----------------------------------------------

• The Chomsky Hierarchy [ pdf ]
• Assignment 2 [ pdf ]
• Chap 12  Limits of Algorithmic Computation
• Some problems that cannot be solved by TMs [ pdf ]

-----------------------------------------------

以下是自己錄的重點提示

雖說是重點提示, 但其實已經涵蓋了今天3小時的上課內容
其實幾分鐘就可以講完的東西....
有時真是由衷希望老師可以好好備一下課....@@

ch11.4

ch12

2016/12/8 Formal Language

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

• Chap 11 A Hierarchy of Formal Languages and Automata
• Recursive and Recursively Enumerable Languages [ pdf ]
• Unrestricted Grammars [ pdf ]

2016/12/1 Formal Language

概略的講完11章
話說我好久沒有錄hw講解了

Formal Language_Assignment 1

其實作業都有解答了, 何必叫我們交呢?


1. hint: dfa的特色就是, 所有的{a,b}都要畫出來(即使是無意義的not-accepted),也就是一個state 都必須split出兩條線, 一條a一條b, 不能多也不能少

所以就連sink也要畫一條線寫a,b指向自己喔!!
(a)少畫了!!

2. hint:
     (1) dfa不允許λ (2)dfa每條路都一定要走出去 

8. 
Pumpimg Lemma複習:
已知一個regular language L 有以下性質, 
有一個數字m(此數字通常指dta的state數目)
若有一個string w屬於L且規定 |w| >= m
那麼w可以被拆成x,y,z三部分, let  w=xyz
其中 |xy| <= m (規定的,這樣等下才能套用pigeon hole) 且 |y|>0 (y一定至少要一個字元)
則一個正規語言會滿足 : { w^i = x y^i z | i是任意正整數 } 全部必須屬於L
若違反了它, 就不是正規語言

Q. 證明L={a^nb^n}不是regular
  (1) 假設L為regular
  (2) 取一個m, 令m=n
  (3) 因為|xy| 必須要<= m, 所以y落在a^n的區間
  (4) 令y=a, x=a^5, z=a^(m-6)b^m
  (5) w^i = x (y^i) z
  (6) 當i>1時, 不符合language a^nb^n的形式, 違反Pumpimg Lemma, 所以L不是regular

所以簡單來說就是,
必須先找一個符合language格式的string w, 再取一個假設的正整數m
並且要保證 w的長度大於等於m, 再想辦法將w切成x,y,z 3部分, 改寫成wi = x y^i z的形式
最後只要能找到一個 i >=0 使得wi不符合 language的string格式,
就可以說它違反Pumpimg Lemma, 所以L不是regular

2016/11/25 Formal Language

複習ch9 TM  並且上到10.2
下周要交作業喔!!

2016/11/17 Formal Language

今天的課程內容十分重要
- - -

8.1
{a^n b^n}{ww^R} 不是regular, 是context-free
{a^n b^n c^n}{ww} 不是context-free, 用pumping lemma證, 但可被turing machine所接受

9.1
所謂algorithm就是一個會停的turing machine

圖靈機: https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA
為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。
現在電腦的組成就是一種圖靈機。

圖靈機是比pushdown automata更強的一種邏輯器,
它可以處理到REC Language以內的問題。
也就是說, REC Language以內的問題, 是電腦可以解的問題。(Fig 11.4,11.5)

Machine	Language
finite state automata(nfa)	Regular
pushdown automata(npda)	Context-Free (CF)
turing machine	Recursively enumerable (RE)

• 何謂deterministic?

         指所有alphabet可能路徑, 最多都只有一條
         例如 alphabet = {a,b}
         每個state最多只會有一條a, 一條b

     

• 何謂halt?

        在TM中, halt states 指的是到達了一個transition state沒有定義的state, 那麼就會終止了

2016/11/17 Formal Language

8.1
{a^n b^n}{ww^R} 不是regular, 是context-free
{a^n b^n c^n}{ww} 不是context-free, 用pumping lemma證, 但可被turing machine所接受

9.1
所謂algorithm就是一個會停的turing machine

圖靈機: https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA
為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。
現在電腦的組成就是一種圖靈機。

圖靈機是比pushdown automata更強的一種邏輯器,
它可以處理到REC Language以內的問題。
也就是說, REC Language以內的問題, 是電腦可以解的問題。(Fig 11.4,11.5)

Formal Language 7.3 自讀

因為11/10期中考周沒去上課, 在此自己讀, 補起一些進度

7.1 介紹什麼是pda (pushdown automata)
它是導入一個Stack來儲存automata的資訊
使得automata本來是infinite的(無限多個), 變成finite(有限個)
進而可以用來表示context-free的語言
(原本的dfa和nfa都只能表示regular的語言, context-free比regular範圍更廣)

7.2 說明npda (non-deterministic pushdown automata)的建構和性質

理論 Thm7.1: 所有context-free的語言, 都可以被npda所接受

這節的題目, 主要是給你一個Grammar, 要你建構出一個npda
答案都只有用transition states表示 (但我個人習慣一定要畫圖, 才比較好思考)

Grammar --> Language --> 畫圖 --> 寫出transition states

如果遇到不能輕易看出language結構的Grammar, 會很難下手畫圖
就要試著將它轉成Greibath Normal Form, 這樣就可以跳過畫圖的步驟, 輕鬆寫出transition state

Grammar --> Greibath Nomal Form --> 寫出transition states

我不確定其他的Normal Form可不可以,
不過像是Chomsky Normal Form我想應該ok, 因為它比Greibath Normal Form更簡單

忘記這兩個Normal Form的話, 請複習一下6.2

可以參考這個網站, 裡面有提到這些Normal Form的設計目的

文法結構一旦改寫成 Chomsky Normal Form ， Parse Tree 就是一棵二元樹，得以設計高效率的資料結構與演算法。

7.3 說明在context-free L裡, deterministic的定義為何?
(翻譯: 什麼能算是dpda(deterministic pushdown automata)?什麼是npda?)

根據Def. 7.3: dpda的條件有兩個
(1)一個狀況(一種(q,a,b)的transition)只能有一條路可以選擇
(2)結束點( (q,空字元,b)的transition set 非空 )的結束字元一個state只有一種, 後面不會拖尾

Formal Language HW7-2 解題

3.

4.

2016/11/3 Formal Language

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

• Chap 6 Simplification of Context-Free Grammars and Normal Forms
• Methods for Transforming Grammars [ pdf ] HW6.1 [ pdf ]

• Two Important Normal Forms [ pdf ] HW6.2 [ pdf ]
• A membership Algorithm for Context-Free Grammars [ pdf ] Sol_6.3 [ pdf ]

• Assignment 1 [ pdf ]
• Key to Assignment 1 [ pdf ] 

- - -

關於作業講解, 我目前還欠4-2, 4-3, 6-2, 6-3 沒有錄
以及這次的 Assignment1

- - -

今天講了6-1~7-1

6-1 講簡化一個context-free grammar的方法
6-2 介紹兩個context-free grammar的Normal Form, 分別是Chomsky和Greibach
6-3 講CYK algorithm
7-1 介紹什麼是push-down automata (npda)


- - -

前言

• given w, G, 判斷一個w是否屬於L(G), 這個過程叫做parsing
• context-free grammar <-> push-down automata

Ch 6.1
簡化一個context-free grammar的方法包含以下三步驟:

• remove empty string
• substitution method
• remove useless sentence(無限loop,走不到final的那些)

關於這個簡化過程,我有打算錄一下視頻介紹, 因為很trivail很容易忘

Ch6.2
Chomsky Normal Form: 所有grammar都符合A->BC or A->a的形式
Greibach Normal Form: 所有grammar都符合A->ax的形式 (很像s-grammar)

Ch6.3 CYK algorithm (用到演算法中的Dynamic Programming)

Ch7.1 push-down automata (npda)
這個很有趣, 我也有打算錄一下視頻, 講一下課本2個例題
不然也可以用key word "push-down automata"去google一下

Formal Language HW5-2 解題

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_5.2.pdf


2.

6.

9.

14. TBD

Formal Language HW6-1 解題

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Chap-6.1.pdf
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_6.1.pdf

8.

13. TBD

Formal Language HW5-1 解題

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Chap-5.1.pdf
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_5.1.pdf

7.(a)

7.(d)

7.(f)

8(a)

8(e)

8(h)

13.

20.

23.(skip)

2016/10/27 Formal Language

花了一小時複習上一堂課的內容
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

- - -

• Parsing and Ambiguity [ pdf ]  HW5.2 [ pdf ]

• Context-Free Grammars and Programming Languages (Skipped)

• Chap 6 Simplification of Context-Free Grammars and Normal Forms

• Methods for Transforming Grammars [ pdf ] HW6.1 [ pdf ]

- - -

參考網址: http://www.csie.ntnu.edu.tw/~u91029/Language.html
發現這網址不錯, 講得蠻細的!

- - -

ch 5-1

• Parsing: 判斷一個string是不是屬於一個Grammar
• 題型: 給一個Grammar,  寫出Language的表示方式
• 一套 Language 可以設計許多種不同的 Grammar 。
• Grammar 理論上必須剛好生成 Language 之內的所有字串、永不生成 Language 以外的所有字串。
• Left/Right-most derivation: 最左/右邊的variable先做
• Derivation(Parse) Tree:

• First node should be root(S)

• every leaf should be terminal.(a,b...)

• every internal node should be variable(A,B...)

• leaf can allow variable

• Partial Derivation Tree:
• sub-tree of  Derivation Tree

- - -

ch 5-2

• s-grammar: 滿足A->ax形式, 且任何(A,a)pair都只出現一次的grammar
• 參考 : http://cs.stackexchange.com/questions/1958/relation-between-simple-and-regular-grammars
• A Simple Grammar (s-grammar) is one in which every production is of the form A→aB1B2...Bn$A\to a{B}_1{B}_2...B_n$ where a$a$ is a terminal and all Bi,i≥0$B_i,i\ge 0$ are non-terminals, and there is only one production with any pair ⟨A,a⟩$⟨A,a⟩$.
• 
  
• Ambiguous
• 我們可以「剖析 Parse 」一個字串，逐字對應至 Grammar 、確立語法，進而判斷原本字串是不是 Language 當中的字串。
• 字串對應到文法時，有兩種以上的對應方式，那麼此文法就稱作「曖昧文法 Ambiguous Grammar 」。

- - -

Formal Language 四大類型

• Regular Language
• Context-free Language: 一個上下文無關文法，有許多條衍生規則。規則裡面是符號、字元、箭頭。「上下文無關」是指符號不會連帶上下文一起衍生。也就是每條規則的左式，只有一個符號，而不會連帶其他符號和字元。
• Context-sensitive Language
• Unrestricted Language

四種語言規律，由規律嚴謹到規律寬鬆排列，前者是後者的特例。

其中 Regular Language 與 Context-free Language ，由於規律十分嚴謹，所以得以設計效率極高的演算法、擁有實務價值。

例如 Regular Language 用於字串匹配、用於驗證字串格式。例如 Context-free Language 用於設計程式語言、用於檢索網頁資料。

- - -

2016/10/20 Formal Language

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

·         Elementary Questions about Regular Languages [ pdf ]  HW4.2 [ pdf ]

·         Identifying Nonregular Languages [ pdf ]  HW4.3 [ pdf ]

·         Chap 5 Context-Free Languages

·         Context-Free Grammars [ pdf ] HW5.1 [ pdf ]

• 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

Formal Language HW4-1 解題

4.1是講rex的closure properties

印象中, 線性代數裡講到封閉性(closeness), 指的是
一個向量空間中的兩個向量
彼此不管怎麼做線性加成, 都不會超出原本的空間, 這種性質稱為closeness

例: u,v屬於S => cu+dv屬於S, where c,d屬於R
一個非空子集合要同時具有向量加法與純量乘法封閉性

- - -
正規語言中的封閉性質
指的是當語言L1和L2滿足regular, 其交集, 聯集, 相乘(concatenation), 補集,取*...的語言也滿足regular

- - -
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/HW4.1.pdf
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_4.1.pdf

這小節幾乎都是證明題, 大概看過而已, 沒有很想證...@@"
證明regular的方法不外乎
(1)直接畫出nfa或dfa
(2)做一些數學運算展開, 然後引用正規語言的封閉性質得證

有想法請一起討論

- - -
2.
寫出transition states作化簡
太過trivial, 略

Formal Language HW3-3 解題

終於借到課本..

在解題之前, 先來複習一下Grammar吧!

V: 所有states (被使用在Grammar裡的)
T: alphabet, 例: {a,b}
S: V中的其中一個, 起始state
P: 終止state

- - -

描述正規語言的方法 (1)automata自動機 (2)Rex正規表示式 (3)Grammar
Grammer是其中一種, 換言之, Grammar可以與automata和rex互相轉換

一個Grammar分成left-linear和right-linear

right-linear:  (產生的string由左往右堆疊, 就像一般的書寫習慣)
    A->xB
    A->x

left-linear:  (產生的string由右往左堆疊)
    A->Bx
    A->x

其中A,B屬於V,     (A,B是states)
x屬於T*                 (x是一個字元組合,字串)

- - -
例:
    A->aaaB  (right-linear)
    A->λ
    B->λ
等同於 (aaa)*
也可寫成:
    A->aaaB
    A|B->λ
或:
    A->aaaB|λ 
    B->λ

"|"是"or"的意思

- - -

right-linear所畫出來的automata和寫出來的rex是我們最熟悉.最直覺的那種
left-linear所畫出來的automata, 箭頭方向要相反, input state和final state要互換
                                    rex要每個段落都逆著寫

例:
S->abS|a
我們可以寫出 (ab)*a
若是 S->Sab|a
我們則要寫出 a(ab)*


- - -

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/HW3.3.pdf

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_3.3.pdf

4.

11.

13.(a)

13.(b)

2016/10/13 Formal Language

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

·         3.3  Regular Grammars [ pdf ]  HW3.3 [ pdf ]

·         Chap 4 Properties of Regular Languages

·         Closure Properties of Regular Languages [ pdf ]  HW4.1 [ pdf ]

--------------------------------------------------------------------------------------------------

• 複習chap3-2

            空集合符號(ㄈㄞ)也可以寫進nfa的箭頭中, 意思是此路不通.不允許
            和空字串(λ)意義完全不相同, 空字串是無條件通過, pass
            將空集合符號寫進去, 有時是為了化成dfa的完整性, 或者寫成正規表示式有時更加方便(?)

• chap 3.3 Grammars

            right/left-linear: 是context free的一個特例

            x: 轉換字元 terminal例: a,b.... 所形成的string

           

• chap4  ragular language的性質

---

昨天沒睡好,今天超想睡....

但是還是覺得,好像沒有很難

不是說Grammar的部分比較難, 為何我沒有這種感覺

先把hw做完, 上課感覺就少了一些樂趣

Formal Language HW3-2 解題

我真是個好人~~~

這次作業量也太多

歡迎一起討論

----------------------------------------------------------------------------------------------

3.

4.

8.

10(b).

10(c).

13(a).

13(b).

16. 懶得看 = =