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