前言與心得整理

我把第六週的部分拆成上跟下，上半部主要解釋P與NP之間的定義與關係．下半部就是要介紹一些證明P=NP的一些理論與方法．

課堂到了最後，其實課堂裡面有許多有用的理論與推導想法，尤其是NP Complete推導的思路，真的能改變解決問題的思考脈絡與方法．相信也可以在以後解決問題的時候，更快可以判別問題的難度．

相關文章

• [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression
• [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages
• [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness

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

問題難度的排序

根據前一個章節的整理，我們可以把問題依照困難度排列(難->簡單)如下: (假設 P不等於NP)

• 無解的問題
• 需要Exponatial Time才能解決的問題
• 多項式時間，還不能決定的問題 (所謂的 NP類問題)
  • 裡面可以再分成 NP Complete(較難) -> NP (較簡單)
• 多項式時間，可以決定的問題 (所謂的 P類問題)

先回過頭看 Polynomial Reduction

在繼續看Cook’s Theorem定義之前，根據NPTEL的影片，其實有很多詳細的介紹．不過針對許多名詞有不同的定義:

首先先回過頭來看polynomial time reducibility定義如下:

假設一個可判定圖靈機(DTM)，從輸入為x處理並且輸出y的處理時間為Polynomial time-bond．如果x屬於L2，我們可以寫L2從L1polynomial time reducible過來的如果滿足以下條件:

• L2 屬於NP類問題，如果L原本是NP類問題
• L2 屬於P類問題，如果原本L是屬於P類問題

這邊也就是解釋，我們可以透過reduction把不同的問題經過歸約(reduction)後到可以處理(或是判斷)為哪一類問題． 就可以回過頭來判斷轉換錢的問題是屬於那一類的問題．

再來，根據原有的plynomial time reducibility，我們會引入另外一個名詞定義polynomially transformable如下:

	A language L1 is polynomially transformable to L2, if there is a deterministic polynomial-time-bounded Turing machine M which will convert each string w1 in the alphabet of L1 into a string w2 in the alphabet of L2, such that w1 is in L1 if and only if w2 is in L2 

• L1 is NP-Complete and L1 polynomially transformable L2. To prove NP L2 is NP-Complete
• Two condition must be satisfied:
  • L2 belong to NP (It is given)
  • Try to find L’ which belong to NP, and let L’ polynomially transformable to L2
    • How?:
      • Because L1 is NP, So L’ must could polynomially transformable L2
      • According to transition theroem:
        • L’ polynomially transformable L1 (because L’ is NP)
        • (given) L1 polynomially transformable L2
        • So L’ must polynomially transformable L2

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

回過頭來試圖去證明 SAT(SATisfiability problem)是NP-Complete，首先我們已經知道SAT是NP類的問題．

(這張圖就是我們的計劃）

想要證明SAT是NP Complete

• 先證明SAT是NP Hard (被Reduction後依舊是NP類問題)
• SAT Reduction 成 3SAT 而 3SAT又被Reduction 成其他 NP類問題
• 可以證明SAT是NP Complete

將所有NP類問題，透過歸約都能轉換成SAT

不過這個時候，為了要證明P=NP我們需要證明任何NP類問題L都能被歸約(Polynomial Reduction)成SAT．以下是我們的目標與方向:

• 已知 L為一個NP類的問題
• 針對L建立一個圖靈機M，M為一個NTM(Nondeterministic Turing Machine)
• 針對這樣的問題L的圖靈機M，我們會有輸入w
• 針對w我們能夠建立出一個布林表示式(Boolean Expression) 並且讓 w 可以透過Boolean Expression來表示．

接下來，就是要建立一個方式可以將所有的問題．將他們的輸入全部轉換成布林表示式．

透過表列式來轉換所有的輸入為布林表示式

概念： 透過查表 K=1,2,…. k 代表第K個輸入

範例:

• 假設輸入的個數有K個(ex: a, b, c, …. k)．
• 那麼如何透過輸入來表示呢． 假設第一個輸入是b．原先的表示會是X_ij=”b”．
• 透過轉換，我們會將所有的輸入多了一個維度K (K= 1…k)於是要表達X_ij 就會改成 X_ij1, X_ij2 … X_ijk ．
• 由於X_ij=”b” ==> 所以 X_ij1= false, X_ij2=true, X_ij3=false …… X_ijk=false
• 另外一個例子: 假設是X_38= “c” –> X_381= false, X_382=false, X_384=true.

透過這樣的方式，我們可以把所有的NP類問題轉換成SAT的問題．接下來我們可以繼續往下做．

更多關於 NP類的問題

接下來的部分會提到更多關於NP類的問題，會提到NP-Hard，Co-NP．主軸會圍繞在透過將3-SAT轉換成其他的問題來解釋更多關於NP的定義．

Tautology Problem

Tautology Problem(也就是恆真式): 指的就是一個表示式一定為真(true)． 比如說:

• X or !X (不論X是什麼一定為真)
• ! (A or B) = !A and !B

Co-NP(反NP)

所謂的Co-NP也就是該語言L的補集L’(Completement)為NP，如此一來就稱L為Co-NP類問題．

這邊也有一個開放的問題(open problem:只尚未解決的問題)，就是if P=Co-NP then P=NP=Co-NP

NP-Hard (NP困難)

NP困難指的是原先是NP類的問題，但是透過Reduction之後才會到目前的問題．看了許多的文章都直接稱它為”就是有NP這麼難的問題”．

透過NP-Hard可以再來回頭看，所謂的NP-Complete

NP Complete(NP完全)

NP完全被稱為是最困難的問題，主要是因為如果一個問題被稱為是NP Complete，它會滿足以下:

• 本身是NP類問題
• 就算被歸約(reduction)過，依舊是屬於NP類問題 (NP困難)

套句簡單的話來說，NP完全的問題相當的困難．因為就算被歸約後，他依舊屬於NP類的問題．所以是相當困難的象徵．

證明其為NP-Complete問題的變換流程圖

接下來會提到，如果遇到一個問題的時候，要如何證明它是NP-Complete?

流程概念會是:

• 先證明該問題為NP類問題
• 透過下圖的轉換方式，可以轉換成任何其中一個．(ex: 歸約成SAT or 3-CNF SAT…)
• 由於SAT與3-CNF SAT都是NP-Complete問題，於是就可以證明它也是NP-Complete

回過頭來看，為何會說SAT問題是NP完全呢? 因為SAT問題可以透過歸約(Reduction)成3SAT(等等會提到)．由於3SAT問題依舊是NP問題，所以我們就可以知道SAT是NP完全問題．

SAT -> 3SAT 轉換

首先回顧一下SAT(SATisfiability problem)，指的是一連串的布林表示式，像下者:

	X1 or X2 

如果透過轉換:

	(X1 or X2 or Y) and (X1 or X2 or notY)

這樣的轉換主要是加入Y並且讓原本的邏輯沒有改變．而類似以上的布林表示式(三個為一組的)就稱為 3SAT． 而上面簡單的轉換方式就是Polynomial Reduction．

順便附帶一下，如果x為以下各種個數的時候，由SAT->3SAT的轉換方式:

• SAT: X:
  • 3SAT:
    • (X or Y1 or Y2) and (X or (not Y1) or Y2) and (X or Y1 ir (not Y2)) and (X or (not Y1) or (not Y2))
• SAT: X1 or X2:
  • 3SAT:
    • (X1 or X2 or Y) and (X1 or X2 or notY)
• SAT: X1 or X2 or X3 -> 3SAT一樣不用轉換
• SAT: X1 or X2 .... Xk
  • 3SAT:
    • (X1 or X2 or Y1) and ((not Y1) or X3 or Y2) and ( (not Y2) or X4 or Y3) ….. ( (not Yk-4) or Xk-2 or Yk-3) and ( (not)Yk-3 or Xk-1 or Xk)

經過轉換，由於3SAT本身被證明依舊是NP類問題．所以可以知道SAT本身是NP困難．也可以說SAT是NP完全問題．

學Automata 對我們的好處

接下來的課程，主要都是不斷的轉換不論是從3SAT歸約成背包問題．或是其他的轉換． 這部分，我就不再去提了…

由於要找轉換，我找了不少其他的學校的投影片與影片．這一篇聯合大學資管系:演算法講義我相當的推薦． 裡面也有提到學P與NP究竟對工作上有什麼樣的影響．(slide p 18)

(引用如下):

假設你在一個公司上班。有一天，上司叫你去為某個對公司很重要的問題找出有效率的演算法。‹結果，你研究了很長的一段時間，沒有任何進展．就在快被解雇的時候，忽然想到世界上很多的電腦科學家正在為旅行推銷員問題(TSP)找尋一個較有效率的演算法。但是，到目前為止卻沒有人能發展出一個在最差情況下，時間複雜度比指數複雜度要來得好的TSP演算法。不過，也沒有人証明出找到這種演算法是不可能的…

你找到了一線生機!! 因為，你只要能証明找出公司問題之有效率演算法的難度和找出旅行推銷員問題的有效率演算法是一樣難的 (亦即：兩者是同一 類的問題)，代表著上司要求你解決的問題也曾難倒很多電腦科學家。

你終於証明出來公司的問題和旅行推銷員問題是同一等級的… （這就是Polynomial Reduction，並且也代表原本的問題是NP完全問題)

程式作業/Homework

homework比較多是考關於Polytime reduction的觀念，還算可以．不過11/02~11/09有Final Exam倒是真的讓我需要K書了．

Final Exam: (update on 11/08)

記錄一些值得再去看看的部分，不要因為考完就忘記:

• DFA_minimization
  • 透過簡化的方式，可以找出相同輸入與輸出下能夠將一些DFA的State做合併．
  • 基本上計算方式透過是否透過相同Input可以到相同的state，來作為合併的挑選．
    • ex: 這張圖 中，c跟d 輸入 1都會到 f，而輸入0都會到e．所以可以合併．

相關程式

這星期主要是實作TM(Turing Machine)，其實要實作圖靈機並不難，只是要找到比較好的圖靈機範例可以測試倒是比較麻煩的．

可以到這裡看看https://github.com/kkdai/tm

參考網址

• Coursera: Automata Course
• 未來數學家的挑戰
• 論P,NP,NP-hard,NP-complete問題 @ 藍色情懷
• 聯合大學資管系:演算法講義
• Youtube: UC Davis- L20: P, NP and Polynomial-Time Reductions
• Youtube: Cook’s Theorem
• Youtube: Cook Levin - Georgia Tech - Computability, Complexity, Theory: Complexity
• P、NP、NP-complete、NP-hard问题闲谈

前言與心得整理

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

相關文章

• [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression
• [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages
• [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness

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

###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

相關程式

本週相關程式，是把NP問題中的PCP拿來當作練習的題目． 本來很好奇為何在網路上沒有找到比較好的解法． 仔細研究才發現PCP(Post’s Correspondence Problems)其實還沒有一個比較好的解法． 主要原因可能因為PCP本身有太多比較難以解決得部分，比如說:

• 判定錯誤的停止條件． 由於PCP是NP問題，而且又是屬於Recursively enumerable language (根據我了解的定義） 所以它無法正確的知道，何時可以停止(halt)
• 目前判斷了循環的一個case，根據我這星期研究PCP循環的case可能目前只發現兩個 (1) 解答循環 (2) 一方的長度無限制延長..

我的解法在這裡，https://github.com/kkdai/pcp 不是一個完整解法，但是持續研究如何解決．

參考網址

• Coursera: Automata Course
• Knapsack Problem: 台師大的中文解釋與範例
• Lecture 29: Tractable and Intractable Problems
• The Class P Slide
• 背包問題(Knapsack Problem)
• P/NP問題
• Youtube: UC Davis- L20: P, NP and Polynomial-Time Reductions
• Youtube: Cook’s Theorem
• Youtube: Cook Levin - Georgia Tech - Computability, Complexity, Theory: Complexity

前言與心得整理

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

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

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

相關文章

• [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression
• [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages
• [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness

第五週課程內容:

###Extensions and properties of Turing machines

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

Multiple Tape Track

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

最常見的就是類似上面圖形的圖形機，上面 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 就是代表要繼續向右移動一個來讀取新的數值．

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

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

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

• 這是一開始的狀態，圖靈機一開始的狀態是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]，最後向右移動一個．

• 這時候由於自身狀態與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] 向右移動一格．

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

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

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

更多圖靈機的架構

• Semi-Infinite Tape (只具有單方向的圖靈機)
  • 以上介紹的是透過兩個無窮(infinite)的track來呈現圖靈機的動作方式．當然也是可以加上一個限制是不允許圖靈機向左(L)移動的．這個時候通常會把兩個tape分開表示成 U/L(代表Upper/Lower) 的資料，而圖靈機本身可以記錄目前要讀取的tape是U或是L．
• Two stack simulate in one Tape
  • 這裡指的是可以透過增加圖靈機的stack到兩個(原本是一個，作為cache) 透過第二個stack來模擬目前位置．

圖靈機的延伸應用

• 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接受的時候．這樣的圖靈機才會停止．

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

• 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)

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

• 最內層是所有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

我們可以透過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

1. (01110, 011)
2. (101, 0101)
3. (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

1. (01110, 011)
2. (101, 0101)
3. (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)的寫法，應該都可以全對．

相關程式

這次的相關程式是寫CYK Alogrithm，恰巧老師在課堂上的範例是比較簡單的．所以整個多項式的展開沒有仔細地講出來．

不過要自己寫出CYK Algorithm for Golang的時候，可就遇到了許多問題． 由於要找CFL的範例來測試CYK，多找了兩個就發現不work． 才發現: 除了 X_11, X_22 以外 要找X_ij的時候其實需要相對應的展開，舉例而言:

	X_12 = (X_11, X_22)
	
	X_13 = (X_11, X_23) 聯集 (X_12, X_33)
	
	X_14 = (X_11, X_24) 聯集 (X_12, X_34) 聯集 (X_13, X_44)

關於演算法的方式，也可以參考這份slide裡面有蠻清楚的算法．

更多詳細，可以參考我寫的cyk演算法: https://github.com/kkdai/cyk

參考網址

• Coursera: Automata Course
• 計算機理論的始祖—圖靈機
• wiki: Recursively enumerable language
• Wiki: Halting_problem
• Wiki: Recursive_language
• Wiki: Undecidable_problem
• Lecture Slide
• Youtube: L12: Universal Turing Machines; The Halting Problem is Recognizable but Not Decidable
• L17: Using Reductions to Prove Language Undecidable

前言與心得整理

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

相關文章

• [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression
• [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages
• [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness

第四週課程內容:

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

相關程式

本週的相關程式，主要是使用第一次的程式作業的內容， 第一次程式作業主要是將RE -> Epsilon-NFA． 作業雖然很簡單，但是作業本身就是一個值得學習的課題．

有興趣可以參考這裡https://github.com/kkdai/re2epsnfa

參考網址

• Coursera: Automata Course
• CYK Algorithm
• PDA: Constructing -NFA’s From Regular Expressions
• Youtube: Regular Expression to NFA
• CYK演算法 wiki
• CYK演算法的推倒影片
• 計算機理論的始祖—圖靈機
• CYK slide in standford

前言與心得整理

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

相關文章

• [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression
• [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata
• [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages
• [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness
• [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness

第三週課程內容:

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

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

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) 主要就是把這三個部分實現出來．

相關程式

本週雖然課堂都在講CFG的部分，但是程式的部分先試著把 ε-NFA完成． 程式碼在這裡 https://github.com/kkdai/e-nfa

幾個註解:

• Epsilon-NFA 其實不難實現，主要是走完input到每一個(guess)猜想狀態後，需要將自己所有擁有的ε路徑(也就是輸入的input為空)把他再走一次．
• 而ε的input也是需要有輸入才能知道ε要走到那些states

參考網址

• Coursera: Automata Course
• Context-free_grammar:wiki
• CNF: Chomsky Normal Form
• Pushdown Automata

##前言

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

###Gobot

講者: kerkerj

slide:

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

閃電秀： Project 52

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

###Go Microserver Use Case

講者: David Hernandez

針對Microservice 講者注重的是:

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