Blog E

October 23rd, 2015

[Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness

前言與心得整理

由於第六週的內容牽扯到P=NP相關理論還有NP-Complete的證明．所以我把內容拆成兩個禮拜，希望能夠更仔細地來了解這個部分．

第六週前半部分的課程內容:

###Intractable Problems

P類問題

接下來會介紹一些需要耗費相當多的時間(指的是處理時間超過指數時間(polynomial-time)的問題．

回過頭來先要定義如何指出圖靈機的時間限制:

T(n): 指的是輸入w長度為n的時候，該圖靈機一定會停止的

這時候就會帶出第一個名詞: P 也就是如何定義一個問題是屬於P類的問題 (Class P problem)

	Class P:  指的是在DTM(Deterministic Turing Machine)下，其T(n)= polynomial-time (指數時間)

關於”P類”問題的範例

DTM可以被來當成是否可以用DFA(Deterministic Finite Automata_來表示其狀態的TM(Turing Machine)．所以其實要尋找類似的範例其實不難，只是該問題必須要是在指數時間才能解決的，課堂上提供的範例如下:

在CFG的 L(G) 給予一個字串w．判斷w in L(G)
- 之前有提過要快的話，必須使用CYK演算法．然後其時間複雜度為O(n^3)

NP類問題

在介紹NP類問題前，雖然課堂上老師直接透過背包問題(Knapsack Problem)來引導NP類問題．不過我個人認為，還是需要簡單的瞭解一下`NP類問題｀的定義:

	Class NP: 指在NTM(Nondeterministic Turing Machine)下，其T(n)為指數時間(polynomial-time)

沒有錯，P類問題與NP類問題最大的差異是TM讀入一個輸入的時候．其反應是唯一的(DFA)或是多重的(NFA)．接下來就可以將背包問題(Knapsack Problem)開始帶入:

什麼是背包問題(Knapsack Problem)

關於背包問題的定義，種類與範例．其實這一篇台師大的文章講得非常好．這裡僅僅簡單的帶過:

背包問題: 將一堆東西放進背包，每一件物品有它的重量與價值，透過有限制重量的背包來取得放入價值的最大化．

解法與時間複雜度: 對於背包問題的解法，一般而言就是透過動態規劃(Dynamic Programming)的方式來找．如此一來: 如果有n個物件，就必須要找出該物件放進背包與不放進背包的價值．所以時間複雜度為O(n * 2^n) (2是因為要計算出現與不出現．必須要反覆計算n回)

P = NP ?

接下來就帶入大家都了解的P=NP這個被稱為史上七大難解問題之一．究竟P是不是相同於NP？其實課堂上也有一些簡單的討論．

以上的圖是來是Wiki，主要是講解如果認為P不等於NP的時候．他的概念是以這樣的方式作為出發來討論．

NP-Complete Problem

首先要討論P是否相同於NP，可以透過一個面向來探討．就是透過NP完全(NP-Complete Problem)．

A decision problem C is NP-complete if:

C is in NP, and
Every problem in NP is reducible to C in polynomial time

這是從NP-Completeness看到比較formal的定義．也就是說，如果我們能夠透過polytime reductions的方式來朝向證明NP-Completeness

Polytime Reductions

Polytime Reductions 又稱為Polynomial-time reduction，以下會解釋這種reduction 的目標與方法:

目標: 如果可以找到一個方式將所有的NP問題歸約(reduction)成語言L，並且能夠找到多項式的解決時間(Polytime)．那麼就可以找到多項式的演算法(deterministic polytime algorithm)來計算所有的NP問題．

簡單的來說:

只要能夠找到一個方式來將所有的NP -> (Polytime Reduction) L
只要能夠找到Polytime Algorithm for L
那麼就能夠推導出其他Deterministic Polytime Algorithm給所有的NP

方法:

先定義有L與M兩種語言
L->(polytime reduction) M
Transducer
- 先做Transducer將原本的資料由長度為n作轉換為x
- 透過Transducer轉換的資料長度會大於n，但是會 <= p(n)
- 將這系列動作既做 T(w) = x
如果w是在L裡面，那麼透過這樣轉換出來的x 必定也在M裡面．

Proof that Polytime Reduction “Work”!!

要如何證明Polytime Reduction是有作用的．

先定義有L與M兩種語言，其中:
- L有輸入w其長度為n，M有輸入x
- L有演算法p(n)， M有演算法q(x)
L->(polytime reduction) M
可以透過transducer轉換出 p(n)=x
可以計算出M的演算法為q(x) = q(p(n))
全部的時間相同 L的計算時間+M的計算時間 = p(n) + q(p(n))
已經知道 p(n)為polytime 並且也知道 q(p(n))也為polytime
p(n) + q(p(n)) 也是 polynomial time

The Satisfiability Problem (SAT)

SAT是NP問題裡面的最常被提到的問題之一，而所謂的SAT就是給予一個運算式來(ex: (x+y)(-x + -y) ) 來尋找該式子為true的狀況，該x與y的組合．這個範例裡面，解答為:

x=0; y=1
x=1; y=0

注意: SAT裡面的優先順序是 NOT(!)->AND(.)->OR(+)

講解Cook-Levin理論 (或稱為Cook’s Theorem)

講解Cook-Levin理論提供了一個方式來證明SAT是NP-Complete(NP完全問題)．

個人很推薦這段兩分鐘的Youtube: Cook’s Theorem，裡面雖然沒有講解Cook’s Theorem的流程，但是把主要精神講解出來．（重點是他只有兩分鐘)

Cook’s Theroem 準則

，Cook–Levin理論提供了很不同的思路去解決SAT是NP-Complete的問題(不過人家也花了十一年)．也就是透過演算法轉換的方式來證明這個問題是NP-Complete，而不是直接去證明這個問題是NP-Complete（from wiki)

已知一個NP-Complete的問題必定存在一個Algorithm，可以在Polytime解決這個NP-Complete問題．
如果能夠把任何演算法透過圖靈機轉換成 Boolean Formula(一個布林方程式是否存在解)
那麼也就能證明這個問題是NP-Complete

NTM(Nondetermistic Turing Machine) for SAT

透過這樣的思路，完整定理是:

	讓L屬於NP，而M代表NTM(Nondeterministic Turing Machine)．我們需要設計一個L，並且使得它的time-bond <= p(n) (其中n是輸入的個數)，並且 p 是 polynomial．

關於詳細的證明流程，我還在仔細研究．目前看了好幾份slide跟課程都無法正常理解．證明 NP-Complete 陷入了一個各家slide 方向與準則相同… 但是沒有一家證明流程是一樣的 XDD

希望下周可以完成．

程式作業/Homework

下週再做Homework

參考網址

October 10th, 2015

[Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability

前言與心得整理

剩下兩週了，就是開始深入了解圖靈機．本週會提到多軌圖靈機的計算方式PCP問題．

此外，本週也開始更多了對於無法判定(undecidable)的問題(problem)的探討．這一系列需要更多的證明，其實如果光看老師課堂上的講義跟講解，其實不是很好了解．

需要相當多的輔助學習跟查詢，我只能就我自己了解的部分．希望能幫助大家，也能給自己做些紀錄．

第五週課程內容:

###Extensions and properties of Turing machines

一開始繼續來探討圖靈機，順便看看有沒有一些衍伸的部分可以加以討論．

Multiple Tape Track

一開始我們都只有定義一個圖靈機是擁有: 一個狀態，一個輸入tape跟相關的動作．但是如果有多個tape track的話，圖靈機該如何處理呢？

`Turing Machine with mutiple track tape`

最常見的就是類似上面圖形的圖形機，上面 BXB 代表的是 data tape(track)，而下方WYZ代表的是marker tape．也就是說下方的資料是用來紀錄目前執行到哪個地方，以便後來做相對應的處理之用．

範例:

首先要注意的是，這個範例僅僅是在課堂上提出來的．並不代表所有的Turing Machine都應該這樣處理．主要還是看如何去處理transition functio與資料輸入的時候該如何查表．

首先要先來解釋一下，幾個transition function的動作說明．再來看δ()之前，我們需要知道幾個符號的定義：

B, X: 代表是輸入的符號B是空白，X某些資料．
a, b: 代表是0, 1(都可以，這裡只是代表數字)
p, q, r: 代表的是狀態(state)
R, L :代表的是要向左移動或是向右移動．
tape指的是資料帶，裡面通常有兩個track，一個是輸入，一個是紀錄marker(或是給TM紀錄輸出) 1 tape = 2 tracks

基礎符號複習好之後，我們就可以開始來看transition function: δ()的意思．

δ([q, B], [B, a]) = ([p, a], [X, a], R):
- 先從一開始來看 δ([q, B], [B, a]) 裡面的
  - [q, B]: 代表的是目前圖靈機的狀態與cache，其中q是狀態，B是cache．
  - [B, a]: 代表的是輸入的tape(其中B為第一個tape, a為第二個type-可以是0或是1)
- 接下來看到等式的右方 ([p,a], [X,a], R):
  - [p,a] 這個代表執行過後的狀態為p，cache變成了a．(注意: 因為a等式左方的a是相同，所以原先是0就是0, 如果是1就取出1)
  - [X,a] 這代表執行過後的tape的變化，變成了[X,a]
  - R 就是代表要繼續向右移動一個來讀取新的數值．

其他幾個就不詳述，只是先列出來等等查表需要用到：

δ([q, B], [B, a]) = ([p, a], [X, a], R)(上面的式子，我只是放在一起方便參考)
δ([p, a], [B, b]) = ([p, a], [B, b], R)
δ([p, a], [B, B]) = ([r, B], [B, a], L)
δ([r, B], [B, a]) = ([r, B], [B, a], L)
δ([r, B], [X, a]) = ([q, B], [B, a], R)

一共是以上五個轉換式，接下來就要看圖說故事了．

`Turing Machine with mutiple track track`

這是一開始的狀態，圖靈機一開始的狀態是q，並且cache的數值為B
這時候要讀取到 [B, 0] 要參考到轉換式 (1) δ([q, B], [B, a]) = ([p, a], [X, a], R)
- 別忘記 [B, a] 可以轉成 [B, 0]， a=0
會將自身狀態改成p並且把cache改成0然後將資料改成[X, 0]，最後向右移動一個．

`Turing Machine with mutiple track track`

這時候由於自身狀態與cache是[p, 0]遇到了[B, 1] 要參考(2) δ([p, a], [B, b]) = ([p, a], [B, b], R)
- 此時 a=0 b=1
這時候會將自身狀態改成 [p, 0]，並且把數值改成 [B, b]也就是維持 [B, 1] 向右移動一格．

`Turing Machine with mutiple track track`

本身資料為[p,0]讀取到[B, B]要參考 (3) δ([p, a], [B, B]) = ([r, B], [B, a], L)
此時會將圖靈機改成 [r, B]並且將資料改成 [B, 0]向左移動一格

`Turing Machine with mutiple track track`

本身資料為 [r, B]讀取到[B, 1]參考(4) δ([r, B], [B, a]) = ([r, B], [B, a], L)
圖靈機維持 [r, B]也不變動資料[B, 1] 向左移動一格

`Turing Machine with mutiple track track`

接下來幾個步驟就不推導了………

圖靈機的延伸應用

Multipletape TM(Turing Machine) 多重資料組的圖靈機
- 一般而言是使用兩個tape，但是這裡提到是使用2K個tape．也就是說有k組的track來給圖靈機操作．根據不同的輸入也可以輸出不同的資料．
Nondeterministric TM 非可判定的圖靈機
- 一般而言，根據輸入與目前狀態是可以判定出圖靈機的下一步，但是在這裡指的是圖靈機本身可以自己決定下一步．也就是說在相同的狀態下給予一樣的輸入可能會引發不一樣的動作．

Closure Properties of Recursive Languages and Recursively Enumerable Language(簡稱 RE Language)

首先要先解釋一下Recursive Lanugage 跟 RE Language的不同:

Recursirve Language:
- 根據定義，Recursive Language每跑一個input都會停下來決定是否接受(accept)．然後繼續讀入下一個文字(string)．
- 一般而言這種語言代表的圖靈機會被稱為是可以判定的(decidable)
- 舉例如下:
  - CFL L= { w = 0^n 1^n } 就算是Recursive Language． L = {01, 000111, 0001111111…}
RE Language: 在RE Language 裡面，這個圖靈機只有接受的輸入才會停止，不然會持續一直運行下去．
- 根據定義，所謂的RE Language也就是指某個圖靈機在某個點會將特定的符號寫回tape(enumerator)並且當成下一個輸入來讀入．
- 一般而言這種語言代表的圖靈機會被稱為是可以認知的(recognizable)，但是是不可以判定的(undecidable)．

詳細的RE Language可以如下:

	Definition 5. An enumerator M is said to enumerate a string w if and only if at some point M writes a word w on the output tape. E(M) = {w | M enumerates w}
	//以上代表， Enumerator 代表輸入w 可以寫回tape
	
	Definition 6. L is recursively enumerable (r.e.) iff there is an enumerator M such that L = E(M).	    
	
	//可以產生遞迴列舉(enumberate)的語言就是RE Language．也是上星期有提到的圖靈機範例．

這裡主要提到關於TM的一些特性(union/concatetion/intersection….)．也就是說當將兩個TM做聯集(union)或是交集(intersection)的運算的時候．面對同一個輸入到底是會輸出接受或是不接受．

Union:
- Recursive Language:
  - Accept (OR), Reject(AND)．也就是說兩個TM都不接受的時候才會才會reject．但是只要有一個接受就會接受(accept)．由於每一次輸入都會停止，所以可以判定是否為接受或是reject．
- RE Language:
  - 由於預設不會停止，所以只有被M1或是M2接受的時候．這樣的圖靈機才會停止．

`Turing Machine with Recursive Language`

這裡要注意，就算是不接受．但是由於是屬於Recursive Language TM依舊會停止(halt)．

`Turing Machine with Recursive Language`

Intersection:
- Recursive Language:
  - 交集就是需要兩個都接受(accept)才能接受．但是一個不接受就會不接受(reject)．
- RE Language:
  - 跟Union一樣，只有接受才會停止．如果有不接受的依舊會繼續的執行．
Difference/Complement:
- Recursive Language:
  - 差集就是需要找M1接受，但是M2不接受的．此時可以找到，因為M2會halt．
- RE Language:
  - 無法找，因為M1接受，M2不接受的時候．由於TM不會停止，無法找出Difference．
Concatetion:
- Recursive Language: - 不能在NTM (Nondeterministic TM)套用Concatenation，因為相同輸入與狀態不一定有． - 都要接受才會接受，但是某一個可能會停止．
- RE Language:
  - 假設輸入為 w=xy 圖靈機有M1 M2 並且已經知道 M1 + M2 ．
  - 所以這樣來說只要判定 M1 能夠接受x ，並且M2能夠接受y，就能夠判定M1+M2能夠接受w 相同的動作產生．
Kleene Star(*):
- Recursive Language:
  - 雖然會中斷(由halt造成的)，但是可以檢查是否每個中斷都是被接受．
- RE Language:
  - 需要額外去由系統來中斷．
Reverse/Homomorphism
- RE Language/Recursive Language是一樣的不再詳述．

Decidability

這一個章節要來了解問題的可判定性要如何決定．也就是針對某個問題是否有相對應的圖靈機(turing machine)可以找到演算法(algorithm)．不過要仔細地瞭解的話就必須要要回過頭來討論”什麼是問題”，就必須要了解在圖靈機裡面對於”問題”的定義．

	問題: 是一個針對無窮集合的個題可以做出的Yes/No 回答

透過利用圖靈機所學到的名詞來表示:

	問題可以說是一種語言(Language)，而裡面所構成的每一個字串(string)都代表對於這個個體(instance)的編碼(ex: 13579 代表第一台，第三台，第五台車子...)．	

對於問題有相當程度的定義之後，就可以回來討論那麼什麼是可判定性(decidability)．

	一個問題被定義是可以判定(decidable)的，如果一個問題有存在著一個演算法(algorithm)可以來回答他． 除此之外，這樣的問題是無法判定的(undecidable)

Bulleye about decidablility

根據這張牛眼圖，可以來了解問題的可判定性與語言之間的關係:

最內層是所有Recursive Language都是可以判定的問題．
- 因為所有Recursive Language的問題，都是跑一個就會停下來(halt)判定．所以可以了解是不是可以判定的問題．
根據剛剛的定義，除了可以判定的問題之外，都屬於無判定的問題．其中包含著 RE Language與 Not RE Language．

關於可以判定與不可判定問題的範例:

以下稍微收集了一些可以判定與不可判定的問題，來了解之間的差異:

可以判定(decidable):
- 已知一個DFA，針對某個特定的語言L．那麼來回答輸入w是否被DFA L(M)所接受?
  - 這是可以判定的問題，因為問題是可結束的(字串有限制)．並且DFA可以正確地回答是否接受與不接受．
- 已知一個NFA，回答輸入w是否被NFA L(M)接受?
  - 一樣是可以接受，因為NFA雖然有多種路徑(path)並不代表無法判定是接受或是不能接受．而且都是在受限制的輸入底下．表示語言本身是會停機來判斷的．
不可以判定(undecidable):
- 兩個CFG是否能產生相同的語言?
  - 這個問題是一個不可以判定的問題，因為CFG可以無限展開．而並須得到可接受才會停止(一般狀況下不會停止，因為CFG可以不停展開)．

關於可判定(Deciding)與可認知(Recognizing)

課堂的Slide沒有提到，但是Wiki上面有查到．加以補充一下:

圖靈可識別語言 (TM recognize):
- 根據wiki，設M是一台圖靈機，若在輸入串w上M運行後可進入接受狀態並停機，則稱M接受串w。M所接受的所有字符串的集合稱為M所識別的語言，簡稱M的語言，記作L(M)。
圖靈可判定語言
- 根據wiki，簡單的定義如下:
  - 語言L與L’的補集(completement) 都是被圖靈機接受的話，就稱為可判定(decidate)語言．
  - 如果只有L 沒有 L的補集，就稱為半可判定圖靈語言．

Universal Turing Machine (UTM)

針對圖靈機本身，可以設計出一個通用(萬能)圖靈機他可以模擬其他圖靈機在某些資料輸入下給予相同的動作與回覆．

###More Undecidable Problems

本章捷會更深入的來探討所謂的無法判定(undecidable)的問題．針對這些會開始有一些基本的定義．

Properties of Language

關於語言的特性(properties)，可以分成兩種:

對於任何語言都是用的特性，被稱為trivial properties．
- 範例：
  - 圖靈機執行100步之後，能不能夠結束並且接受?
除此之外，只能某些語言適用的．都被稱為是non-trivial properties．
- 範例:
  - 這個圖靈機的結果會不會有字元?
  - 這個圖靈機接不接受”hello”這個字元? (RE Language TM 只知道接受，但是無法確認不接受)

其實透過Properties的定義，主要是要推導出 Rice’s Theorem

	Rice’s Theorem:  Any nontrivial property about the language of a Turing machine is undecidable.

也就是說，語言特性中具有non-trivial properties的圖靈機，是屬於無法判定的．

換個角度來說，其實每個Language Properties可以被視為是該圖靈機的問題(problem)．那麼對於該圖靈機是否為可以判定的依據，就可以透過它能接受的語言特性(properties)．

Reduction and Transducers

Flow of reduction and transducer

我們可以透過Reduction與Transducer來對問題可否判定做一個解讀．要解釋Reduction與Transducer就必須要透過這一張流程圖．裡面包含了幾個名詞解釋:

Reduction:
- 如同這張圖，原先的語言L(假設接受字串w) 透過某種Reduction．可以找出 L’並且可以接受x(x也是透過某種轉換油w->x)
- 如果我們發現 L'是可以判定(decidable)的，我們也可以說 L 是可以判定的．
Transducer
- Transducer是一個轉換器，可以將w轉換成x．並且可以讓x被L’所接受．

通常而言，這個定理都是這樣使用:

	如果L是不可判定，那麼該語言的補集L'必定也是不可判定．

Post’s Correspondence Problem

接下來要說明另外一種不能判定(undecidable)的問題．不過這系列的問題與圖靈機無關，可以先把相關的定義都先放到旁邊．

所謂的PGP問題，是在尋找倆倆配對的問題．首先題目會給予你許多字串．舉例來說:

Pairs

(01110, 011)
(101, 0101)
(1110, 10111)

那麼他會問你，是否可以透過以上的配對組合找出完全相同的串列使得

	w_i1, w_i2, .... win = x_i1, x_i2, .... x_in | i= 1...k

這樣講有點繞口，簡單的來說就是要透過給予的1~3 的配對來搭配出兩個完全相同的序列串．

比如說: 1+3+2 會產出

           1    3       2 
	A:[011  10][111  0][101]
	B:[011][10  111][0  101]  

可以看得出來，A跟B所有出現的字元都相同，最後的長度也相同．接下來要講怎麼計算:

第一步一定都需要放第一個配對，因為只有第一組的左右是起始相同的，換句話說如果有其他起始相同，其實不需要從第一組開始．左邊放在A, 右邊放在B．會得到以下的部分

         1    
	A:[011  10]
	B:[011]

第二步之後，我們就可以隨便從1~3挑選．由於可以看到A比B多出了 [10]這個字元．我們來挑選 1~3之間可以找到． 3 的右邊 [10111]的開頭是 [10111] 是否和我們需要的．試著放上去:

           1    3   
	A:[011  10][111  0]
	B:[011][10  111]

目前為止都沒有出現問題，再來發現A比上B多出了 [0] 來挑選1~3發現第二個的右邊是以[0101]作為開頭．於是我們這樣放:

           1    3       2 
	A:[011  10][111  0][101]
	B:[011][10  111][0  101]  

A 跟 B 兩個是等長並且是相同的．我們就可以回答這個PGP的問題是Yes．

MPCP for Reduction

接下來會透過PCP這種問題，來解釋Reduction的用處．首先我們會先定義更嚴格的PCP定義，稱為Modified PCP:

MPCP: 基本定義跟PCP一樣，只是第一步必須挑選pair 第一個．

接下來，我們會來將MPCP簡化成PCP，其實課堂裡面的slide講得很清楚，不過我們就直接做一次:

MPCP Pairs to PCP Paris

(01110, 011)
(101, 0101)
(110, 10111)

首先拿出(1)，在左邊的每個字元後面加上*，在右邊的每個字元前面加上*
- (1’) (0*1*1*1*0*, *0*1*1)
第(2)個之後，把每個字元的後面加上*:
- (2’) (1*0*1* , 0*1*0*1*)
- (3’) (1*1*0*, 1*0*1*1*1*)
套完之後，我們還需要增加一個額外的
- (4) ($, *$)
最後還有一個結尾要加上special pair，這邊是參考原先的(1)，只是把左右兩邊每個字元前面都加*:
- (5) (*0*1*1*1*0, *0*1*1)

這樣就完成了…..

這邊的做法是，把剛剛對於PCP的Pair數據改寫到MPCP後．透過Transducer(也就是上面這種轉換方式，簡化為PCP後．）主要是為了達成以下的定義:

	能夠在MPCP裡面判定(decidable)的問題(內容為w)，透過以上得轉換後，必定可以在PCP找到可以判定的語言(x)

換句話來說，

	已知MPCP ->(reduction) PCP:
	如果可以證明PCP 是undecidable的話，那麼也可以判定MPCP是undecidable．

接下來有另外一種簡化方式，簡單來說整個簡化流程圖為:

	Lu -> (Transducer) Lm(MPCP) -> (Transducer) -> Lp (PCP)

這邊的證明有點繁瑣，先留給大家有興趣再來鑽研．

程式作業/Homework

本週沒有程式作業，不過有homework．而Homework都是圖靈機的題目，算是五週以來最簡單的了．只要了解Turing Machine與 ID(Instantaneous Descriptions)的寫法，應該都可以全對．

參考網址

October 10th, 2015

[Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages

前言與心得整理

進入到第四週，這個章節會透過深入了解PDA(Pushdown Automata)來導入CYK演算法與計算機的基礎- 圖靈機(Turing Machine)．算是我一開始就相當期待的課程．

第四週課程內容:

Equivalence of PDA’s and CFG’s

主要這個章節是會提到如何將CFG(Context-Free Grammar)轉換成 PDA(Pushdown Automata)，首先先來符號介紹:

L(G): 屬於CFG G所以符合的Language L
我們想要透過 PDA P來找出一個轉換方式可以產生 N(P) = L
- 在這個 PDA(P)裡面有:
- start node q
- 所有的輸入symbol 屬於 G
- 相同的stack會存入的就是symbol所以也是從G挑出來
- 一開始的symbol也是從G挑出來．

範例:

CFG: S->Aa ; A->cc
Stack start symbol: S
Input: acc

以下分開成δ()與stack狀態

δ(q, a, S), stack: [S], input: cc (輸入a 進去了)
- 這時候會從input 移除a, S 可以轉換成 Aa
- 去除掉a stack剩下 [A]
δ(q, c, A), stack: [A], input: c
- 這時候轉換A->cc
- 並且一個c 被input 修除
δ(q, c, c), stack: [c], input: ε
δ(q, ε, ε), stack: [ε], input: ε

於是結果為Stack變更的流程為: [S]->[aA]->[A]->[cc]->[c]->ε

Convert PDA to CFG

接下來要來將PDA的轉換式，轉換成CFG．根據定義我們會從

    L = N(P)

來建立相同L的 CFG G，並且滿足 L(G) = L = N(P)．

首先這裡有一個假設 [pXq] 指的是從pstate透過輸入X可以到q state．

範例:

    δ(p, a, X) contains (q, ε) 可以表示  [pXq]->a

就是所有從p輸入a的時候
此時stack裡面有X．而且可以到達q
使得stack 為空 (ε)．就可以求得 [pXq]->a

範例

    δ(p, a, X) contains (r, Y) 可以表示  [pXq]->a[rYq]

是p透過a會先到達r(此時會先把X從stack pop出來)
而且stack 剩下Y(表示有push Y)
所以是production 是 [pXq]->a[rYq]
也就是說如果要達到q還必須要輸入Y才能夠從r到達q．

The pumping lemma for CFL’s

首先先來回顧一下，什麼是pumping lemma:

在一個Regular Language其中有著n個狀態，在字串長度w > 輸入個數的時候，總能夠找到 xyz 符合:
w = xyz
xz <= n
y > 0
For all i>=0 xy^i z is in L

同樣的在CFG(Context-Free Language)一樣也能夠找到Pumping Lemma只是有不同的是:

    同樣的RE Pumping Lemma定義下 y 有兩段 z=uvwxy

在一段CFL之中，有著n個數字．如果字串z>=n則存在z=uvwxy 其中
vwx <= n
vx >=0
For all i >=0; uv^i wx^i y in L

Decision and closure properties for CFL’s

如何證明字串w是不是屬於L(G)，可以使用CYK algorithm． (它具有的時間複雜度為 O(n^3))

CYK Algorithm

CYK演算法可以來計算某些輸入字串是否符合CFG(Context-Free Grammar)．如同上勉提到的算法．如果最後計算出來的symbol沒有非終端的符號(non-terminal symbol，一般而言就是S)的話．就代表字串不能被CFG所產生．

一般而言，要計算某段文字是否能被CFG來產生，需要透過回朔法(backtracking)原本需要指數時間 O = C^n ．但是使用CYK可以把所需要得時間縮短到 O = n^3．算是有相當程度的優化．

直接透過範例來解釋會比較容易了解:

範例:

    S->AB, A-> BC|a, B->AC|b, C-> a|b    input string w= ababa

解題流程

首先先找 X_ii:
- 拿出第一個input a，來找X_11:
  - 找出 A-> BC a 取出 A
  - 找出 C-> a b 取出 C
  - 於是 X_11 = {A, C}
- 拿出第二個input b, 來找X_22:
  - 找出 B-> AC b 取出 B
  - 找出 C-> a b 取出 C
  - 於是 X_22 = {B, C}
- 拿出第三個input a，跟第一個解法相同得到 X_33 = {A, C}
- 拿出第四個input b，跟第一個解法相同得到 X_44 = {B, C}
- 拿出第五個input a，跟第一個解法相同得到 X_33 = {A, C}
接下來要找 X_ij
- 舉例要找出 X_12，需要參考 X_11 跟 X_22
  - 第一個symbol 要找 A 在X_11中(第一個)，B在X_22中(第二個)．能夠找到 AB的就是 S-> AB 於是得到S
  - 第二個symbol 要找 A 在X_11中(第一個)，C在X_22中(第一個)．能夠找到 AC就是 B-> AC 於是得到 B
  - 答案就是 X_12 = { S, B }
- 舉例 X_23，需要參考 X_22 = {B, C}與 X_33 = {A, C}
  - 第一個symbol 要找 B在X_22(第一個) 找 C在X_33(第二個)，能夠找到 A->BC 於是得到Ababa
  - 第二個symbol 要找 B在X_22(第一個) 找 A在X_33(第一個) 沒有找到能夠推導出 BA的，於是沒有．
  - 答案: X_23 = {A}
- 再舉例一個 X_34，需要參考 X_33={ A, C} X_44={B, C}
  - 第一個symbol 找 A在X_33 (第一個)再找 C在X_44(第二個) 於是要找 AC 得到B
  - 第二個symbol 找 A在X_33 (第一個)再找 B在X_44(第一個) 於是要找AB 得到S
  - 答案: X_34 = { B, S}
依此類推….
如果要找 X_13 就得找 X_12跟 X_23 其他步驟同上
依此類推找到 X_15 為 {A}
由於X_15的結果不含{S}，而是只有A．所以我們知道 w=ababa不存在這個L(G)裡面

Turing Machine

一開始先講解資料與程式相關的部分．其實編碼就可以視為是一種automata的轉換方式．接下來有一些名詞解釋:

Finite Set 有固定長度的集合，裡面找不到任何一對一的關係．只是資料的集合．
- 範例:
  - {A, B, C} 是一個 Finite Set而他的基數(cardinality)為3 (也就是集合中的元素個數)
Infinite Set 代表一個集合有一對一的關係，不論是對於自己或是其他集合．
- 範例:
  - {1, 2, 3, 4, ….} 其中 1<->2, 2<->4
Countable sets 其中有一對一的正整數關係(並不是代表全部數字都是正整數，而是代表可以用正整數找出他們的關係)
- 範例:
  - {0, -1 1, -2 2, ….} 其中 -1跟1 為 -i 與 i 的關係（i為正整數)

Turing Machine Theory

目的: 透過Turing Machine Theory可以證明特定的Language是否含有algorithm

下面橫向的A,B,C,D 為 type是一個由已知的輸入符號({A,B,C,D})所構成的無止盡的集合．根據這張圖，Turing Machine Theory主要是根據輸入的symbol(下方的ABCD)與本身的狀態來改寫symbol(就是會改寫下方的輸入)並且檢查是否會到達final state．這樣的計算方式可以被用程式語言來實現，而且這樣的計算比較簡單與易懂．

基本原理很像PDA(Pushdown Automata)不過TM(Turing Machine)本身會改寫symbol．圖靈機(Turing Machine)被認為是電腦架構的原型，主要有以下幾個因素：

輸入: 透過Type的輸入，可以將資料輸入到電腦．
處理: 圖靈機會根據輸入來做相對地移動或是動作（改寫資料）
狀態: 這也是圖靈機跟其他不同是，一般而言輸入1或是輸入0應該都要能夠期待有相同的結果．但是由於有狀態概念，所以相同輸入在圖靈機不一定會有相同的動作(除非狀態也相同)．

範例

主要需求:
- TM來判別一連串的輸入是否有1，如果遇到輸入為1就停止並且接受．
- 全部輸入為 {0, 1, B(空白)}
邏輯:
- 如果遇到輸入為0，繼續向又去找
- 如果遇到輸入為B，退回一部，並且將B改成1
- 如果遇到輸入為1，停止並且接受．
輸入:
- 全部輸入為{BB00BB}，從第一個0開始．

透過轉換式(transition function)來表示:
- δ(q, 0) = (q, 0, R) (其中R代表方向，向右) 此時輸入剩下 0BB
- δ(q, 0) = (q, 0, R) (其中R代表方向，向右) 此時輸入剩下 BB
- δ(q, B) = (q, B, L) (其中L代表方向，向左) 此時輸入剩下 01B
- δ(q, 0) = (q, 0, R) (其中R代表方向，向右) 此時輸入剩下 1B
- δ(q, 1) = (f, 0, R) (其中R代表方向，向右) 此時輸入剩下 B，因為到達f所以結束．
透過ID( Instantaneous Descriptions)來表示目前狀態
- 不同於PDA裡面的ID，這裡的ID是透過 q00 來代表 (目前狀態是q 即將輸入的symbol 為 00)
- q00 (goes to) 0q0 (goes to) 00q(注意其實q右邊還有blank)(goes to) 0q01 (goes to) 00q1 (goes to) 000f

Formal Definition of Turing Machine Moves

δ(q, Z) = (p, Y, R)
- 可以寫成 aqZb (goes to) aYpb
- 如果Z等同於B(blank)也可以寫成 aq (goes to) aYp (b被消除)
δ(q, Z) = (p, Y, L)
- 可以寫成 aqZb (goes to) apYb
- 對於任何X aXqZb (goes to) apXYb

演算法(Algorithm)可以視為是一個TM(Turing Machine)，並且能夠到達的被接受與停止(f)的狀態．

L = L(M) 如果M為一個演算法，我們可以說L是一個Recursive Language．所以我們可以說:

CFL(Context-Free Language)是一個recursive language．使用CYK演算法．

程式作業 (CYK演算法)

這星期的作業是講CYK演算法，其實不算是太困難，不過題目裡面的資料呈現方式相當的詭異．竟然是用三個陣列來表示． S->AB 這樣的概念．這樣在寫作上會比較困難，

作業本身就是要熟悉這樣的資料方式．與表現symbol的方式來做出CYK演算法．我將會在下一個章節的相關程式使用Go來完成CYK演算法．

主要概念與解法提示:

記得要從 X_11 X_22 X_33… 先算
再來算 X_12 X_23 X_34
比較需要注意的是，由於資料表示用 [0]表示S [1]表示B．所以 S必定在B的前面，但是這個問題要解決，不然計算答案會錯．
這邊要提醒，其實除了 X_11 X_22 以外，其他計算的時候都需要有展開多項式

’’’

k= j-i
X_i,j = (X_i,i+k-1,  X_i+k,j) | k=1  聯集  (X_i,i+k-1,  X_i+k,j) | k=2....	   '''

更多部分可以參考 wiki

參考網址

October 2nd, 2015

[Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata

前言與心得整理

進入到第三週，前兩個章節都是在介紹可以透過RE(Regular Expression)來表示的語言．這一次就是無法透過RE來表示的語言(CFG: Content-Free Grammar)還有相關的定義與運算．

第三週課程內容:

Context-Free Grammar

Content-Free Grammar(以下簡稱CFG) 是一種可以透過符號來敘述語言，可以表達比RE更多的語言(但是不是全部)．特別是在表現巢狀結構的語言．

以下只介紹正式的定義:

Terminals: 定義好的符號，類似語言中的alphabet．
Variables: 又稱為non-terminals，有限集合的符號，另一種表示語言的方式．
Start Symbol:類似於RE中的start state．
Production(投射): 也就一種對應的關係，通常表示為 ->．其中左邊是 variables 右邊是 terminals跟variables的字串． ex: S-> {0, 1}
Derivations(推導): 主要就是將CFG由start symbol開始，並且開始將variable投射出相對應的variables或是terminals其中的代表符號是=>．
- S->01 S->0S1 則 S=>0S1(將S->0S1)=>00SS11(將一個S->0, 另一個S->1)=>000111
Iterated Derivation: 符號為 =>* 如同Kleene Star定義一樣，這個代表推導為0或是更多．
- a =>* a (就是代表任意個a)
- a =>* b and b=> c 則 a=>* c
Sentential Forms (句型): 指的是字串可以由Start Symbol加上 terminal 或是 variables．
- S =>* a 那麼 a就可以被稱為 sentential form (因為a是一start symbol，而且加上variable a組合而成．)

以下是一個簡單的範例:

CFG : { 0^n 1^n | n >=1 }

terminals: {0, 1}
variables: {S}
start symbol: S
product: S -> {01} S -> 0S1
關於Iterated Derivation範例:
- S -> 01; S->0S1
- 則 S=> 0S1 => 00S11 => 000111
- 由前面的式子推導出來， S可以推導出 S或是沒有S 所以 S =>*S
  - 於是 S =>* S =>* 0S1; S=>* 00S11 ; S=>* 000111

Backus-Naur Form

程式語言的語法，通常會被寫成BNF(Backus-Naur Form)．這裡會開始把CFG的一些定義轉換到BNF上面，才能方便我們開始用在程式語言上面．

變數(variables)寫在 <...>裡面
Terminal通常會用粗體或是底線
::= 就是代表 CFG裡面的production ->
| 就是 OR
如果symbol緊接著...:代表 Kleene Star (*)的意思
如果是...在輸入{}之後，代表有更多的輸入． (類似function parameter裡面的 ...)

範例:

L -> a[{ab} ...] 開始推導:

L -> aB ; B=[{ab}…]

L-> aB ; B-> C ε; C={ab}… (其中 [{ab}...]代表出現 0或是以上個 {ab} 所以先用ε替代出0) 而 {ab}...代表的就是 1個或是以上

L-> aB ; B-> C ε; C=AC; A={ab} (由於出現 {ab}… 一個或以上，可以用符號 C->AC 因為 A={ab} C可以繼續推導出A或是AC)

解答就是 L->aB B->C ε C->AC A->{ab}

關於 Derivation的順序(Leftmost or Rightmost)

根據定義，其實BNF可以是Leftmost 也可以是 Rightmost．但是必須要在Derivation上面寫清楚．

    L ->_lm A[{ab}...] (_lm代表 leftmost 左邊作為優先順序)

Parse Tree

定義

Parse Tree:是拿來表達CFG的樹狀結構，其中:
根節點(root): 為CFG中的Start Symbol
葉節點(Leaves): 一定都是terminals或是ε
中間節點(iterate node): 可以是variable或是terminals

(image from Coursera Automata Course)

以上是一個範例圖形，主要是敘述 S-> SS | (S) | ()，可以看出來:

葉節點一定為(或是)，必須要中間節點才會出現Variable S
Start Symbol 也就是Root 是 S
其中的yield為此parse tree的trabersal 結果 yield : ( () ) ()

Leftmost Induction 與 Rightmost Indction

如果要用Leftmost Induction的順序來分析Parse Tree:

範例:

Induction: Xi =>*_lm Wi
Start Symbol: A
於是乎:
- A=>_lm X1 X2 X3 … Xn
- A=>_lm W1 X2 X3 … Xn (將Xi換為W1)
- A=>_lm W1 W2 W3 … Wn
- 最後的結果為 W1 W2 … Wn

Ambiguity Grammars

其實就是簡單指有 |的 grammar 比如說 S-> S | {S}就是．

範例：

    B-> (RB|ε  R-> )| (RR

一開始會覺得這個很難解讀，甚至完全不瞭解該如何解讀這段題目．其實他應該要拆解成兩段敘述:

B-> (RB|ε 代表的是 B 可以推導出 (RB 或是 ε (代表結束)
R-> ) | (RR 代表 R可以推導出 ) 或是 (RR

透過課堂給的範例，我們來跑一次

    B-> (RB|ε  R-> )| (RR
            
    Input: (()) ()

分析的流程如下(走Leftmost方式):

一開始從 B開始
輸入(:
- 能找到的只有 B-> (RB 於是替換成 (RB
輸入(:
- (RB 將其中的 R替換成 (RR 於是結果是 ((RRB
輸入):
- ((RRB 將其中的R(由於是Leftmost，所以是挑左手邊第一個R) 換成 ) ，於是結果是 (()RB
輸入):
- (()RB 跟上一步一樣，改成 (())B

….之後分析方式都一樣．最後結果是 (())()．

這一個章節談的是 Ambiguity Grammars但是 ` B-> (RB ε R-> ) (RR不算是．因為輸入為 (或是) 都只會找到一個不會有兩個比如說 B-> (RB (`．

Derive Nothing

這裏是指CFG有可能造成持續有variable而無法完全轉換成symbol的狀態．拿以下的例子: 注意: 大寫字母是Variable，小寫字母代表是Symbol

    S -> AB | C, A -> aA | a, B-> bB, C -> c

由這個例子可以看到:

由start symbol S -> AB之後， A 可以透過 aA 或是在轉換成 a來轉換成symbol (這裏稱為reach symbol)．
但是 B -> bB 於是持續有個variable B存在．
這樣的CFG無法轉換出全部symbol的語句．

Elimilate Variable

這裏主要是消除一些造成Derive Nothing的grammar，在上面的例子：

    `B -> bB`

會造成無窮的variable B產生，所以我們必須要把B消除掉．

    S -> A|C, A-> aA | a, C->c

這樣就能確保能夠Derive Symbol．

Nullable Symbol

所謂的Nullable Symbol指的是某些Variable會推導出ε(epsilon)．也就是說 A->ε，同時我們也稱為A->ε這樣的production叫做ε-productions．舉例來說:

            S -> AB | C, A -> aA | ε, B-> bB | A, C -> c

根據以上的例子 A -> aA | ε所以我們可以說 A 是 Nullable Symbol．
由於 B-> bB | A．所以 B->A->ε． B 也是Nullable Symbol
推導出 S->AB 所以 S -> AB -> εε．S也是Nullable Symbol

Elimilate ε-Productions

由於 ε-productions會產生出Nullable Symbol．所以我們必須要把會產生ε-productions的grammar消除掉．使用的流程如下:

    S -> ABC,  A-> aA|ε , B-> bB | ε , C-> ε

由於推導出 A->ε B->ε C->ε 導致 S -> ε．
找出新的grammars 透過S找出所有會找出epsilon變數(以這個為例: S, A, B ,C 都是，但是如果S->ABCD, D->d 的話就不需要找D的宇集合)的宇集合，並修改如下
- S -> ABC AB AC BC A B C
- A-> aA (已經把ε去除)
- B->bB (已經把ε去除)
- C -> ε (先不去除ε等等要拿來消去grammar)
去除掉所有的ε-productions，由於剩下 C -> ε，消去所有跟C有關的Grammar
結果如下:
- S -> ~~ABC~~ AB AC BC A B C
- 推導出 S -> AB A B
- A-> aA
- B->bB

Unit Production 跟 Pair

Unit Production 指的是grammar剛好能夠 product 到一個variable．也就是 A => * B．所以 S=>* S, A=>*A．

Pair A, B 寫成(A, B)代表存在著unit production A=>*B．

Pair同時具有遞移律，如果 (A, B)且 (B, C)則我們必定能夠找到 A=>*B , B=>*C 根據law of induction必定能夠推導出 A=>*C．所以也存在著 (A, C)．

範例:

    S→AB|Aa; A→cD; B→aCb|C|A; C→D; D→a|b|c  
    找出所有的pair               

一開始就能得知，必定存在著 (S, S), (A, A) (B, B) (C,C) (D, D)
接下來要找unit production可以找到 B->C B->D B->A C->D 於是我們取得 (B, D), (B, D), (B,A) (C, D)
所有的Pair 即為(S, S), (A, A) (B, B) (C,C) (D, D)(B, D), (B, D), (B,A) (C, D)

Cleaning Up a Grammar

所謂的Cleaning Up grammar就是必須要消除:

No useless symbol
No ε-Productions
No Unit Productions

Chomsky Normal Form

CFG 如果滿足以下兩個條件，可以被稱為是CNF(Chomsky Normal Form):

只存在兩個variable在body A->BC
或是只存在一個terminal A->a

或是 S->ε

  定理: L 是CFG，L-ε必定存在一個CFG是屬於CNF (L- ε 代表語言減去ε之後的其他集合)

這個定理也表示，任何的CFG(除了ε)一定都可以轉換成CNF的格式．

舉例

    A->BCDE

先轉換成 A-> BF, F->CDE
A->BF, F->CG G->DE 即完成

Pushdown Automata

Pushdown Automata(PDA)主要是透過stack來存放某些symbol(可能是代表marker或是狀態，不侷限)．其實整體架構不難，只是何時要把symbol push進stack何時需要把symbol pop就是靠原本的定義．

類似Pushdown Automata wiki用更多個參數的宣告來表示push/pop

(圖片來自課堂 Automata Course)

範例:

在這樣的宣告下，這個PDA主要是幫助我們檢查全部的輸入(input)中，0與1的個數是否成對．

基本宣告如下:

PDA 可以接受 { 0^n 1^n | n>=1 }
q是start state
輸入為1的時候會走到 p state並且pop
f 是 final state
關於symbol 的宣告:
- Z 代表stack 底部，代表1與0的個數相同．
- X 代表一個0輸入，每輸入一個0, 就push 一個X進stack
關於transition function 的表示
- δ(q, 0, Z)={(q,Z)} 代表從q 狀態開始，輸入為0，其中symbol為Z． {(q,Z)} 左邊代表透過input 0所走到的狀態q，右邊代表stack狀態有一個Z．
- δ(q, 0, X)={(q,XZ)} 代表從繼續從q出發輸入0，到達q．其中stack為ZX
- δ(q, 1, X)={(p,Z)} 代表從繼續從q出發輸入1，到達p．其中stack為Z．注意第三個參數會提到要pop X．

ID: Instantaneous Descriptions

ID: Instantaneous Descriptions是一個算式可以幫助我們知道總共輸入多少，進行到哪個階段，並且也顯示stack狀態的一個算式．

(q, w, a) 其中q代表目前狀態，w代表剩下的輸入，a代表stack狀態(top在左邊)．

其中每個ID之前或用一個 “Goes-To”(符號沒有了 XD要用圖形) 符號代表下一個推導．

範例

(q, 000111, Z) “Goes-To”
(q, 00111, XZ) 輸入一個0並且放入一個X到stack頂端
(q, 0111, XXZ) 輸入一個0並且放入一個X到stack頂端
(q, 111, XXXZ) 輸入一個0並且放入一個X到stack頂端
(q, 11, XXZ) 輸入一個1並且從stack頂端移走一個X
(q, 1, XZ) 輸入一個1並且從stack頂端移走一個X

**如何判斷輸入的字串有沒有被PDA所接受? **

確認 ID最後stack為狀況為Z並且狀態走到f 也就是整個ID為 (f, ε, Z)

程式作業

主要是實作 RE -> ε-NFA的程式．其實大部分已經都完成好了，主要是考觀念關於 union， concatenation跟 closure 大概五分鐘就搞定（如果概念沒問題的話….)，基本觀念重新敘述如下:

union: ex: A union B
- 主要是會產生兩個新的狀態，
- 新的start state分別連到原先 A start state 與 B start state．
- 新的fianl state分別會被A與B的final state所連接．
- 連接的輸入都是 ε

concatenation: ex: A concatenation B
- 主要是將A與B的圖形連接，A的final state會連到B的start state
- 當然連接的輸入都是 ε

closure: ex: Closure(A)
- Closure 主要就是要將幾個ε-translation function 加上去
- 建立兩個新的狀態
- new start -> orignal start
- orignal final -> new final
- final->start
- new start -> new final
- 當然連接的輸入都是 ε

其實可以參考slide 5 (14~16) 主要就是把這三個部分實現出來．

參考網址

October 1st, 2015

[研討會心得][GTG15][Golang]第十五次的Golang Taiwan聚會

##前言

這次的Golang Taipei Gathering #15 我有參與閃電秀．

###Gobot

講者: kerkerj

slide:

Golang Taipei Gathering #15 - 進擊的 Gobot! from kerkerj

主要是講姐Gobot的一些指令，Gobot提供相當好的介面可以直接去控制GPIO跟一些相關的機器． RPI/Ardurino甚至提供指令直接控制Sphero． Gobot 提供直接的方式可以控制COM port 與RS232直接對Ardurino與其他設備來溝通．

閃電秀： Project 52

不好意思～～我的閃電秀….

Project52 from Evan Lin

###Go Microserver Use Case

講者: David Hernandez

針對Microservice 講者注重的是:

How to handle big request in short time
What if some service down –> circuit breaker
有展示Goconvey的測試，感覺很酷．

September 26th, 2015

[Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression

前言與心得整理

進入到第二週，不知道會不會有更困難的主題出現．寫筆記寫著寫著，發現自己筆記內容比原本老師講的還要多，代表自己不懂得真的太多，需要不斷的補充資料來讓自己更清楚．

第二週課程內容:

Regular Express 基本定義與運算

符號定義:

通常顯示E來表達一個regular expression，而L(E) 就表示一個regular expression 能表達出來的語言(language)．

Language的運算: (Union/Concatenation/Kleene Star)

Union (U): 就是把兩個language做一個簡單的聯集．
- ex: {01, 11, 101} U {10, 11, 101} = {01, 10, 11, 101}
Concatenaion (LM): 把兩個language做一個連接，但是注意這裡跟字串的concatenation是不同的．基本定義而顏，把語言L跟語言M連接在一起就稱為LM． LM = wx | w in L and x in M．
- ex:
  - L = { 01, 11}
  - M = { 10, 11}
  - LM = { 0110, 0111, 1110, 1111} 也就是第一個L元素配上第一個M元素，第二個L元素配上第一個M元素．繼續類推．
Kleene Star (*): 就是regex裡面的*，表達任何子集合在L中與空集合或是一個以上的子集合的聯集． L* = {ε} U L U LL ...
- ex: L = {01, 11} L*= {} or {01, 11} or {0101, 0111, 1101, 1111} ....

Regular Expression定義

a是一個symbol, 如果a是一個regular express(記作RE)，則 L(A) = {a}
L{ε} = {ε}
L(empty set) = empty set

將Langugage的運算套用過來，其中E1 跟 E2代表兩個RE:

U運算： L(E1+ E2) = L(E1) U L(E2)
Concatenation: L(E1E2) = L(E1)L(E2)
Kleene Star (*) : L(E*) = (L(E))*

以下列出一些範例：

基本定義: L(0) = {0}, L(01) = {01}
Union: L(01+0) = L(01) U L(0)= {01} U {0} = {01, 0}
Concatenation: L(0(1+0))= L(0)L(1+0) = {0}{1,0} = {01, 00}
Kleene Star: L(0*)={ε, 0, 00, 000, ... }
複雜一點的綜合運算： L((0+10)*(ε+1)) = L((0+10)*) L(ε+1) = L({0, 10}*) L(1)
- 根據以上得結果，所有的Language，不論是0開頭或是1開頭，1結尾，但是只要沒有兩個連續的1就符合．
- ex: {01} {0001} {0101010101}
- 連續兩個1不再其中，因為是 ({0} + {10})* U {1}

將RE用ε-NFA表示:

要將RE(Regular Expression)用ε-NFA來表示，基礎的概念如下:

    邊線(arc)代表一個symbol，而路徑可以表示成 a, ε, empty set

(image from coursera Automata Course)

套用基礎運算的上如下:

Union: 就是一個分支的圖形

(image from coursera Automata Course)

Concatenation: 就是一個連接的圖形

(image from coursera Automata Course)

Closure: (CL) 就是一個自己與自己迴圈的圖形(簡單來說 Kleene Star -> Closure)

(image from coursera Automata Course)

將RE用DFA表示

概念上就是依照以下的方式:

    狀態(state)也就是我們節點
    而邊線(arc)就是我們會出現的symbol
    所以DFA所能接受的路線(path)就是我們要的語言(language)．

拿前一章節出現過的圖，舉例來說:

這個DFA要表達的A->B 的Language可以是{11} 或是 {0011} 或是 {0001} 也可以說L(E)={1,01,0101...}
所以這個RE可以表達為E=(0)*1+(10)*1 也就是說
- 0可以出現一次或是無限次，但是最後一定要有一個1
- 或是(01)可以出現一次或是無限次，但是最後一定要接著1

k-Path

這邊指的K-Path指的是要透過狀態i到達狀態j其中只能經過k(其中k代表1…k, 比如說k=2 也就是 0, 1, 2)能到達目的狀態的路線，先用簡單的DFA來舉例，舉例而言．請注意所謂的 k-path不代表必須經過k，是可以不經過的．

由狀態A->B的k-path

0-path 也就是A->B不經過任何其他狀態，結果1
A-path 也就是A->B可以經過狀態A，結果0*1+1，也就是可以走無限個0然後走到B或是直接走到B．
B-path 可以經過B，也可以經過A(這裏假設 A = B - 1)，當然可以都不經過．所以推導出來也就是整個DFA的RE：也就是 0*1+(10)*1

關於 k-path的推導題

k-path通常指的是由狀態i 到狀態j 必須經過k狀態（其中k代表的是 0, 1, 2, … k)．

    記作 R_ij^(k) (其中 ij 為下標，k為上標)

所以R_ij^(k) 也可以換成思考為:

路徑由 i到j 不經過 k (k-path是可以不經過k，也代表經過k個數是0)
或是:
- 路徑由i到k
- 路徑k走到過所有k-1的狀態回到k
- 路徑由k走到j

如以下圖:

透過以上的圖示，可以推導出公式如下：

    R_ij^k = R_ij^(k-1) #也就是 i->j 不經過 k
            +  R_ik^(k-1)   R_kk^(k-1)*  R_kj^(k-1)   # 就是 i->k, k-k, k->j   

UNIX (REGEX) Regular Expression

接下來，課程談到介紹UNIX上面常使用的Regular Express．這邊大家應該比較熟悉，只把幾個常用符號整理一下:

[a-c] 指的是 a, b, c 都可以
[a-z] 同理可證，就是所有小寫字母．
“+” 指的是出現至少一次．
“*” 指的是零次或是以上．
“?” 指的是零或是一次．

還有一些跟RE與NFA跟DFA的轉換可以筆記一下:

UNIX RE 先轉換成 ε-NFA (並且擁有自己的final state)
設定一個新的start state 並且將原本的ε-NFA 作為 ε-translations
透過ε-translations就可以轉換成DFA
透過DFA可以再度的轉換到RE去

詳細的轉換方式，可以參考以下圖片

Decision Properties of Regular Language

####定義:

Decision Properties of Regular Language指的是是一個演算法來作為正式敘述一個語言的方式．

舉例:

Is string w in language L?
Are those two language the same?

####The Emptiness Problem

指的是給予的Language是不是符合這個RE也就是說，假設是DFA給予的語言，能不能夠從start state 跑到 final state．

####The Infinitness Problem

指的是RE中是否有發生迴圈的圖形．而檢查圖形是否為 Inifitness 最簡單的方法是:

    如果全部的狀態個數為n， 只要可以接受輸入language個數，而且 m >n．  代表就會有迴圈發生．

就會像是以上的圖形一樣．

Pumping Lemma

需要先定義一下，什麼是Pumping Lemma，根據wiki上面解釋如下:

    RE中一個長字串，其中有一段文字有出現超過一次以上．

簡單的說，Pumping Lemma 也就是上面圖形所呈現的狀態．

那接下來就要顯示．基礎定義：

全部的狀態個數為n，輸入的語言為w
w = xyz
xz] <= n
- 這邊解釋一下 xz 代表的是出現的alphabet個數，比如說 x=abca z=bcdb |xz|=abcd
y > 0
For all i>=0 xy^i z is in L

這幾個定義裡面，最重要的其實是|xz] <= n．因為找出y的方式不是在找出重複的，而是要確認|xz]．以下舉一個例子:

Pumping Lemma 範例:

ex: 語言L他的狀態為1,2,3 輸入為{a, b, c} 輸入為 {abacca}，他們的狀態變化是 1(a)->2(b)->3(a)->2(c)->1(c)->3(a)->2 找出他的w =xyz的pumping lemma

解法：

首先試著去找出第一個重複的狀態．也就是1->2->3->2->…
這時候抽出2->3的輸入{ba} 即為 y
同理，可以分解出前面的x={a} z={cca}．同時驗證 xz = {ac} <= 3

如何驗證兩個DFA L與M 是否equivalence

要證明兩個DFA是否equivalence，需要透過以下方式:

計算 L product M
找出 w 滿足L也滿足M(滿足:accept 代表能由start state到final state)
這樣就可以證明 L與M是 equivalence

接下來，要如何做 L product M方法如下:

假設Q1 是 L的所有狀態， Q2是M的所有狀態
找出Q1與Q2的start state [q1, q2]
開始iterate 每一個transition function，並且找出product DFA
透過最後的Product DFA找出一個w 可以由start state走到final state．
即代表兩個DFA L與M是equivalence

(image from coursera Automata Course)

範例:

起始點為[A, C]
走第一個transition input 0
- [A, D]
走第二個transuion input 1
- [B, C]
依照這個方式… 慢慢建構出所有的DFA如上圖右

Closure Properties of Regular Language

這裏主要是敘述定理，還有一些證明方式，主要定義如下:

L 跟 M 都是 Regular Language (可以使用regular expression表示出來)

進行以下的操作，並且證明結果都是屬於regular language:

Union: L U M 仍然是regular language (可以用regular expression來表示)
- R是L的regular expression， S 是 M的regular expression．L U M = R + S．可以得知 `R + S仍然是regular expression (根據 union law)
Concatenation / Kleene Star: 根據以上的方式， RS (concatenation)，及 R* , S* 仍然都符合regular expression (concatenation and kleene star law)
Intersection: L intersect M 代表裡面的 R S要找出交集的部分，使用的方式是將兩個圖形做 product 然後找出product的regular expression 即為 L intersect M．
Difference: L - M 也會是符合regular language．根據上一則的方式，透過 product DFA LM 可以找出一個流程是 L 可以由start state跑到 final state但是 M不行．由於該流程regular expression 是存在於L的其中一個，所以該流程也是符合regular expression．所以 L - M 也符合regular langugage
Completement: completement in L = sigma(Σ)* - L sigma(Σ) 是regular languge 當然Σ* 也是regular languge根據剛剛的difference 定理 L - M 也符合regular langugage自然而然 Σ* - L 也是．
Reversal: L^R 表示Reversal 代表的是 L = {0, 01, 11} L^R = { 0^R, (01)^R, (11)^R}= { 0, 10, 00}
- 需要注意的是 (0)^R = 0 同理可證 (1)^R = 1
- 相關的Reversal Law:
  - (F+G)^R= F^R + G^R
  - (FG)^R = G^R F^R
  - ((F)*)^R = ((F)^R)*
- 範例: E = 01* + 10* + 1 找出 E^R
  - E^R = (01*)^R + (10*)^R + 1^R
  - ` (1)^R 0^R + (0)^R 1^R + 1`
  - ` (1^R)* 0 + (0^R)* 1 + 1`
  - 1*0 + 0*1 + 1
Homomorphism: h(L)就是透過某些轉換是來把原先的alphabet做一個替換．
- ex L = {0, 10, 11} h(0)->A, h(1)->B 則 h(L) = { A, BA, BB}
Inverse Homomorphism: h^-1(L)是將把透過 h(L2)的結果轉換回 L2. h(L) = L1, h^-1(L1)= L

[Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness

前言與心得整理

相關文章

第六週前半部分的課程內容:

P類問題

NP類問題

什麼是背包問題(Knapsack Problem)

P = NP ?

NP-Complete Problem

Polytime Reductions

Proof that Polytime Reduction “Work”!!

The Satisfiability Problem (SAT)

講解Cook-Levin理論 (或稱為Cook’s Theorem)

程式作業/Homework

相關程式

參考網址

[Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability

前言與心得整理

相關文章

第五週課程內容:

Multiple Tape Track

範例:

更多圖靈機的架構

圖靈機的延伸應用

Closure Properties of Recursive Languages and Recursively Enumerable Language(簡稱 RE Language)

Decidability

Universal Turing Machine (UTM)

Properties of Language

Reduction and Transducers

Post’s Correspondence Problem

MPCP for Reduction

程式作業/Homework

相關程式

參考網址

[Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages

前言與心得整理

相關文章

第四週課程內容:

Equivalence of PDA’s and CFG’s

Convert PDA to CFG

The pumping lemma for CFL’s

Decision and closure properties for CFL’s

CYK Algorithm

Turing Machine

Turing Machine Theory

Formal Definition of Turing Machine Moves

程式作業 (CYK演算法)

相關程式

參考網址

[Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata

前言與心得整理

相關文章

第三週課程內容:

Context-Free Grammar

Backus-Naur Form

關於 Derivation的順序(Leftmost or Rightmost)

Parse Tree

定義

Leftmost Induction 與 Rightmost Indction

Ambiguity Grammars

Derive Nothing

Elimilate Variable

Nullable Symbol

Elimilate ε-Productions

Unit Production 跟 Pair

Cleaning Up a Grammar

Chomsky Normal Form

Pushdown Automata

ID: Instantaneous Descriptions

程式作業

相關程式

參考網址

[研討會心得][GTG15][Golang]第十五次的Golang Taiwan聚會

閃電秀： Project 52

[Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression

前言與心得整理

相關文章

第二週課程內容:

Regular Express 基本定義 與 運算

符號定義:

Regular Express 基本定義與運算