Formal language and automata - ch2

Ch2. Finite automata

Deterministic Finite Accepter(dfa)

● deterministic accepter
  ○ definition:
    M = (Q, Σ, δ, q₀, F)
      Q: set of internal state
      Σ: set of symbol (input alphabet)
      δ:  Q × Σ → Q transition function   (表示state的轉換)
        e.g.  
         δ(q₀, 0) = q₁
         即在q₀ state 、當input alphbet為0時，移動到state q₁
      q₀ ∈ Q: initial state
      F: set of final state

     每一步都要清楚定義(每個state都要考慮所有alphbet的可能)

  ○ operate:

     1. 一開始在initial state(q₀)
     2. 每次移動(move)，讀入一個input alphabet，根據讀到的input和當前的state，移動到下一個state
     3. 讀完所有input時，若在final state則為accept，否則為not accept

  ○ transition graph:

    state: 以圓圈表示
    transition function: 以箭頭表示
    input: 箭頭上的label
    initial state: 一個圓圈有一個箭頭沒有前一個state
    final state: 雙圓圈

      ※ transition graph 可以表示所有的dfa
    e.g.
      M = ({q₀, q₁, q₂}, {0, 1}, δ, q₀, {q₁})
     with transition function δ:
        δ(q₀, 0) = q_0,   δ(q₀, 1) = q₁
        δ(q₁, 0) = q_0,   δ(q₁, 1) = q₂
        δ(q₂, 0) = q_2,   δ(q₂, 1) = q₁

  ○ extended transition function:
     δ(q₀, a) = q₁
     δ(q₁, b) = q₂
⇒ δ*(q₀, ab) = q₂

● Language and dfa:

   dfa可以接受的language即為所有dfa產生的字串的集合

   L(M) = {w ∈ Σ*: δ*(q₀, w) ∈ F}

  Language L is regular language if and only if there exist a dfa M使得
    L = L(M)

Nondeterministic finite accepter (nfa)

● definition:
    M = (Q, Σ, δ, q₀, F)
      和dfa類似，除了transion function不同:
      δ:  Q × (Σ ∪ λ) → 2^Q transition function   (表示state的轉換)

● 和dfa不同處:
          1. transition function 對應出來為一個set，而不是單一state (next state有多種可能性)
              e.g. δ(q₀, a) = {q₀, q₁}  

          2. transition function 第二的element可為λ                              (可不消耗alphabet切換到下一個state)

          3.  δ(q₀, a) 可為empty                                                               (transition 沒有定義)

          4. 可接受的string為：只要可以停在final state的string
● extended transition function: same as dfa

● transition graph:
 

                δ*(q₁, a) = {q₀, q₁, q₂}

                δ*(q₂, λ) = {q₀, q₂}

                δ*(q₂, a) = {q₀, q₁, q₂}

                note: 每個state本身都有一個λ cycle  (即透過λ 可在原本的state)

● language:

   nfa可以接受的language即為所有nfa產生的字串的集合

   L(M) = {w ∈ Σ*: δ*(q₀, w)  ∩ F ≠ φ}

  即w可以走到final state (有一個state即可)

Equivalence of deterministic and nondeterministic finite accepter

● equivalence of finite accepter:
   two finite accepter are same

   L(M₁) = L(M₂)

  if both accept same language

● equivalence of nfa and dfa:

    dfa 為一種nfa

    nfa 可以轉為dfa

      利用powerset ，新的graph的vertex為nfa的powerset

  ○ nfa轉換為 dfa:
          1. 創造一個新的graph G從 {q₀} 開始
          2. 對於所有G上的vertex {q_i, q_j, ..., q_l}，和一個 a ∈ Σ
              找出所有從 {qi, qj, ..., ,ql} 經過a 可以到的vertex，並標為一個新的state
          3. 重複2直到沒有新的vertex
              (必定結束，因為新的graph最多2^Q |Σ| edge)

          4. 標上final state: 任何有包含原本final state的vertex在新的graph均為final state
          5. 若 λ 也accept，則q₀也是final state

        e.g. 

           nfa

            第一步：

            第二步：

            完成所有vertex：

            完成圖：

Reduce the number of state

● indistinguishable/ distinguishable state:
   two state are indistinguishable if
       δ(p, w) ∈ F implies δ(q, w) ∈ F
   and
       δ(p, w) ∉ F implies δ(q, w) ∉ F

    for all w ∈ Σ*

● reducing produce :

  ○ produce mark:

     1. remove 所有無法到達的state

     2. 對所有state進行區分，分成final state和非final state (兩者為distinguishable，同set裡為distinguishable)

     3. 對所有indistinguishable state區分：

         若有 a ∈ Σ 使得兩個state p, q

            δ(p, a) = p_a

            δ(q, a) = q_a

       且p_a 和q_a為distinguishable，則p q為distinguishable

即
     對於所有字母a
     若p q經過接受a產生的state不再同一個set(distinguishable)，則p q不是同個state (distinguishable)

     4. 重複3直到沒有新的state被區分

  ○ produce reduce: 利用procedure mark找出所有相同的state，並根據相同state建立新的dfa

     1. 找出相同state: {q_i, q_j,...}，在新的dfa M' 中視為一個state

     2. 對於原本的dfa所有transition rule δ(p, a) ＝ q: 找出在M'中，p 和q 所在的state p' 和q'
         建立新的transition: δ(p', a) = q'

     3. 重複2直到原本的的dfa所有transition rule完成

     4. 標示initial state: M'中，包含initial state 的state即為initial state

     5. 標示final state: M'中，包含原本dfa final state的state均為final state

Formal language and automata - ch1

Ch1. Introduction

Mathematical preliminaries and notation

● Set (集合)

 A collection of element x₁, x₂, x₃, ..., x_i without any structure other than membership

  E.g. 

   S = {0, 1, 2}

   S = {a, b, ...,z }

   S = {I : i>0, I is even}

 ○ Property: 
   ※ disjoint: S1 ∩ S2 = 空集合
   ※ subset: a set S1 is a subset of S if 所有element 均為S的 element
   ※ proper subset: (同subset不包含兩個set 相同的情況)
   ※ powerset: the set of all subset of a set S
     (每個element 都是一個集合 )
   ※ Universal set (U): set with all possible elements
   ※ Empty set (φ): the set with no element
   ※ partition: 一個set分成多個subset，每個set互disjoint
   ※ finite: element of a set is finite
   ※ infinite : element of a set is infinite
   ※ size of a set: number of element in a set

 ○ Operation: 
   ※ Union
   ※ Intersection
   ※ Difference
   ※ Complementation
   ※ Demorgan's law:
     1. -(S1 ∪ S2) = (-S1) ∩  (-S2)
     2. -(S1 ∩ S2) = (-S1) ∪ (-S2)
   ※ Cartesian product:
     S1 * S2 = {(x, y): x ∈ S1, y ∈ S2 }

● Function and relation

  ○ Function: assign a element in S1 to S2 (f: S1 -> S2)

   (S1中的element 只能有一個對應，否則為relation)

   S1: domain

   S2: range

  ○ Relation: S1中，一個element 有多個對應

   E.g. Equivalance 

● Graph and tree

  ○ Graph: a construct consist 2 set: V (vertex) , E (edge)

         Each edge is a pair of vertex

      ※ walk: a sequence of edge in the form: (vi, vj), (vj, vk), (vk, vm)

        (Edge的後一個點為下一個edge 的前一個點)

      ※ length of a walk: walk經過edge 的數量

      ※ path: edge沒有重複的walk

      ※ simple path: 沒有點重複

      ※ cycle: 一個walk 開始和結束的vertex相同

      ※ simple cycle: 沒有點重複

      ※ loop: 一個edge 開始和結束的點相同

      ※directed graph: edge 有方向性

   ○ tree: a directed graph without cycles

      ※ root: 到任何vertex 都有一條path

      ※ leaves: 只有incoming edge

      ※ Child (vi->vj) vj 為vi的 child

      ※ parent (vi->vj) vi 為vj的 parent

      ※ level: 從root 開始到特定vertex的path經過的edge數

      ※ height of a tree: tree 中最大的level

     

● proof of technique: 

   ○ proof of by induction

   ○ proof of by contradiction 

     

Three basic concepts

● Language:

  ○ component:

      ※ alphabet

         Σ = {a, b}

      ※ string

        w = abaaa 
       (λ : empty string)

       →substring:
       →prefix:

       →suffix:

       (注意prefix和suffix都有空字串)

       →Σ* : set of 用Σ 造的字串

       →Σ+ = Σ - {λ}

  ○ definition:
    Language(L): a subset of Σ*
    sentence: a string in L

  ○ operation:

      ※ concatenation: 將字串或元素相接

      w = a₁a₂a₃...a_n ; v = b₁b₂b₃...b_m

       ⇒wv = a₁a₂a₃...a_nb₁b₂b₃...b_m
      L₁L₂ = {xy, x ∈ L₁, y ∈ L₂}

      ※ reverse

       w^R= a_n...a₂a₁

       L^R = {w^R: w^R ∈ L}

      ※ repeat:
       wⁿ : 重複string n次(接在後面)
      ( w⁰ :empty string)
       L⁰ ={λ}
       L¹ = L
      ※ length: |w|

      ※ complement

       -L = Σ* - L

      ※ star-closure

       L* = L⁰ ∪ L¹ ∪ L^2...

      ※ positive-closure

       L+ = L¹ ∪ L^2...

● Grammar:

  ○ definition:

      ※ grammar

      G = (V, T, S, P)

         V : variable (set)
         T : terminal (set)

         S : start variable 

         P : production (set)

      ※ production rule:
        x → y 

      ※ apply grammar, derive
        w = uxv
        z = uyv
        w ⇒ z (w derive z)
        w₁ ⇒ w₂ ⇒... w_n (w₁ w_n)

      ※ L(G) = {w ∈ T* : S  w}

         L(G) is the language generated by grammar G

● Automata:

  ○ essential feature:
     ※ input
     ※ storage
     ※ control unit (internal state)

  ○ deterministic automata v.s.  nondeterministic automata

    deterministic : 每次都只有一種可能性(一種move可以走)

    nondeterministic : 有多種可能性

Ref: PETER LINZ, An Introduction to formal languages and automata Fifth edition

Shell指令

<持續新增整理中>

● sh
 以子程序執行bash
 (執行後變數不會存在)
 -n : 讀取指令，但是不執行
 -v : 讀取指令時，將指令同時輸出到螢幕上
 -x : 在執行程式時，將指令和參數輸出到螢幕上

e.g.  sh sh01.sh

● man
 指令查詢及說明

  左上角的代號:
   1. 使用者在shell環境中可用的指令
   2. 系統核心可以呼叫的函式與工具
   3. 一些常用的函數(function)與函式庫(library)，大部分為C的函式庫(libc)
   4. 裝置檔案的說明，通常在/dev下的檔案

   5. 設定檔或者是某些檔案的格式

   6. 遊戲(games)

   7. 慣例與協定等，例如Linux檔案系統、網路協定、ASCII code等等的說明

   8. 系統管理員可用的管理指令

   9. 跟kernel有關的文件

● grep
 分析、搜尋字串

  -c : 計算找到"字串"的次數
  -r : 遞迴讀取所有資料夾下的檔案
  -v : 反向選擇，即沒有包含"字串"

● alias
  替指令命名別名

  e.g.  alias lm='ls -al'

● history
  列出使用過的指令
  (~/.bash_history)

● mkdir
  建立新目錄

  -p : 建立多層目錄（遞迴建立）

● rmdir
  刪除空目錄

  -p : 連同上層空目錄一起刪除

● unset
  取消變數或函式

  -v : 取消變數
  -f : 取消函式

● set
  沒有參數時，顯示所有 shell 變數
  有參數時，設定shell的屬性

● export
  自定變數轉換成環境變數
  e.g. export PATH

● read
  讀取鍵盤輸入

  -p : 後面接提示字元
  -t : 後面接等待秒數

  e.g.

   read -p "input:" input0
   #input0 = 鍵盤的輸入

● touch
  修改檔案時間或建置新檔
  當檔案不存在，則建立新檔案
  當檔案存在，預設將三個時間(access time/ modification time/ status time)都更新為目前時間

  -a : 只更改access time
  -c: 只修改檔案的時間

● last
  顯示最近登入的使用者

● chmod

  更改權限

  

  rwx : 讀、寫、執行 

  ugoa : user, group, other, all

  e.g. chmod 770 file1

  e.g. chmod u=rwx,go=rx file2

  e.g. chmod a+w file3

● time(1)
  計算指令時間

  e.g. time [options] command [arguments...]

● time(2)
  得到時間(秒數計算)

========================
● Ctrl + C
  終止目前命令

● Ctrl + D
 輸入結束(EOF)

● Ctrl + S
  暫停螢幕輸出

● Ctrl + Q
  恢復螢幕輸出

● Ctrl + Z
  暫停目前的指令

● Ctrl + M
  Enter

● Ctrl +U
  將整列命令刪除

==============================

● ` `內的指令會先被執行

==============================

語法
● if [  ]; then
     ##########
  elif [  ]; then
     ##########

  else

     ##########
  fi

● case $變數  in
  "變數內容")
    ;;  #結尾需兩個
  "變數內容")
    ;;
   *)
     ;;
esac

● function fname() {

}

● while [  ]
do
    ####
done

● until [  ]
do
   ####
done

● for var in CON1 CON2...
do
    ####
done

● for (( 初始值; 限制值; 執行步階 ))
do
    ####
done


==============================

● $0 : 程式本身
● $1 : 程式的第一個參數
● $# : 程式的參數個數
● $@ : 代表「 "$1" "$2" "$3"」  所有參數
● $? : 前一個程式的回傳值

==============================
 檔案:
● /etc/shell  :  定義可以用的shell
●


參考：

鳥哥的Linux 私房菜

manual page