前言與心得整理

進入到第四週，這個章節會透過深入了解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的測試，感覺很酷．

前言與心得整理

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

相關文章

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

第二週課程內容:

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

相關程式

我也把NFA的概念加以實現成一個小工具．放在https://github.com/kkdai/nfa

原本根據定義是無法實現，但是我透過BFS還是可以做出來．只是還在思考是不是有遺漏的案例．

參考網址

• Coursera: Automata Course
• Regular_language: wiki
• Pumping_lemma_for_regular_languages wiki

前言

其實Go 1.5的正式公布後，最吸引人的就是與其他語言的相互合作．透過的可能是編譯成c-shared library．但是其實我個人最期待的，當然就是使用go mobile．

最近他們把相關的範例跟工具都弄的差不多，並且有一了份相當詳細的教學在這裡．

簡單流程:

由於教學寫得很清楚，我這裡簡單的把事情都跑過一次．注意：你需要有Go1.5．

//抓取go mobile tool
go get golang.org/x/mobile/cmd/gomobile

//初始化gomobile，可能會花一點時間
gomobile init

//編譯gomobile裡面的範例
//這會在本地端直接編譯出 basic.app 只要透過xcode 複製到手機上即可(需要有開發者付費帳號)
gomobile build -target=ios golang.org/x/mobile/example/basic


//如果要把go package編譯成iOS可以用的framework
//這會在本地端編譯出一個hello.framework
cd $GOPATH/src/golang.org/x/mobile/example/bind
gomobile bind -target=ios golang.org/x/mobile/example/bind/hello

//直接在xcode拿來使用即可
open ios/bind.xcodeproj

來個iOS簡單範例 (11/17更新)

這裡提供一個簡單的範例，主要也是測試一下幾個主要的疑慮:

簡單的範例程式碼在這裡，這裡有直接的playgroud

package gomobile01

import (
	"fmt"
)

type Goomobile struct {
	Data string
}

//記得要有constructor 不然到時候你無法自行透過 NSObject init 來建立這個物件
func New() *Goomobile {
	return &Goomobile{Data: "Default test"}
}

func (g *Goomobile) GetData() string {
	fmt.Println("test go ")
	return g.Data
}

這時候建立這個iOS framework 指令是 (假設專案寫在kkdai/gomobile01)

$ gomobile bind -target=ios github.com/kkdai/gomobile01

然後會產生一個gomobile01.framework 把他拉進xcode專案． 以下提供如何使用的方式:

//載入該framework	
#import "gomobile01/Gomobile01.h"

這裡是使用的方式，切記要使用Constructor不要使用 [[xx alloc] init]

    GoGomobile01Goomobile *gb = GoGomobile01New();
    //Default data is @"Default test"
    [gb setData:@"Data...."];
    NSString * str = [gb GetData];
    //str = @"Data..."

已知可以支援的部分

• 基礎的運算與簡單的資料格式當初參數 (int, string)
• 支援structure跟method
• 可以跑net/http但是記得別直接拿rpc.Client或是http.Client當作public

相關限制

目前試著編譯幾個有在使用的package發現有以下的問題，可能需要解決．

• []slice, map, interface{} 比較進階的資料格式不支援 (可能也不能轉換到iOS)
  • 同理可證，一些package裡面的變數也不要放在parameter裡面．只支援基礎資料格式．
• 即便是簡單的string, int不支援public global variable．
  • var TestVariable string 不被允許
  • 但是var testVariable string 是可以允許的
• const目前還不支援 (gomobile: not yet supported, name for const)
• structure need public: 如果要使用某些物件，要能夠在Objective C上面使用就必須要記得改成public (big-case)
  • 這會發生問題imported and not used: YOUR_PACKETGE
  • 一般而言，public寫法是正確的，但是把struct改成private其實也不是不可以．
• 無法同時bind兩個package: 由於裡面的記憶體處理或是其他處理的問題．
  • 一般而言如果你跑了 gomobile bind target=ios A_PACKAGE 然後把a.framework拉近xcode在跑gomobile bind target=ios B_PACKAGE再把b.framework拉進專案，前面一個a.framework就會出現問題(不能跑)． 詳細的解釋在這裡issue 12245．還沒有比較好的解法．
• [11/17] 如果要在Structure 必須要建立相關的constructor (NewXXX())．

##參考文章

• gomobileでiOSアプリをビルドする手順まとめ
• GoMobile Wiki
• 關於Gomobile bind 的相關注意事項(官方)
• Golang Talks for Gomobile “Go on Mobile”

####將所有m透過預設Object C++來編譯:

• 設定->LLVM 7.0 -> Compile Source As -> Object-C++

這裏的設定比起單獨點選每個.m再來改成ObjectC++更有優先權．

設定額外的Include Path

• 設定-> HEADER_SEARCH_PATHS (記得改HEADER_SEARCH_PATHS就好)．
• 記得要使用 $(PROJECT_DIR)/../../../include，而不是單純的 ../../../include不然會找不到．

避免發生 Undefined symbols for architecture x86_64

這是因為你嘗試要跑模擬器的編譯而你編譯出來的static library並沒有x86_64的選項．這邊的修改方式有幾個:

• 增加x86_64 到”Build Setting”->”Artchitectures”跟”Valid Artchitectures”
• 或是修改”Build Setting”->”Build Active Architecture Only”改成No

Bitcode enableing

Bitcode是xcode7新的功能．但是如果使用xcode新的專案都會遇到warning，關閉的方法就是在App去關閉，當然如果要使用這個功能，就得每個library都要打開bitcode．