Regular Expression-javascript

可以參考
http://www.w3schools.com/jsref/jsref_obj_regexp.asp

● /pattern/modifiers
  ○ pattern
    ◎ 運算元：
      [abc]：找到有abc字元(a或b或c)
      [^abc]：不包含abc字元
      a|b    ：找到a或b
      n+    ：找到n至少一次
      n*    ：找到n 零次或一次以上
      n?    ：找到n 零次或一次
   
   
    ◎ 特殊符號：
      \w ：word-character (a-z, A-Z, 0-9,_)
      \W：非word-character
      \d ：digit (0-9)
      \D：非digit
      \s ：空白
      \S：非空白
      \b：在開頭或結尾
      \B：不在開頭或結尾
      \n：換行符號
      \r： carriage return
      \t： tab
   

  ○ modifiers

     i: 忽略大小寫

     g: 找出所有pattern，而非只找到一個就停

     m: multiline matching，和換行有關

● javascript RegExp Object：
  ○建構：

    var res = new RegExp(pattern, modifiers);

  ○Method：

    1. exec()

    2. test()：  match時回傳true，否則回傳false

    3. toString()

e.g.

  var res = new RegExp(/[2-9]/g);
  if (res.test(input_txt.value))
  {
    alert("Sorry! " + input_txt.value + " is not accepted");
    clear_in();
    return;
  }

● replace()：  (String method)

1.  str.replace("str1", "str2")：str1被取代為str2

2.  str.replace(/pattern/modifiers, "str1")：match的pattern取代為str1

3.  str.replace(res, "str1")：利用ResExp object，將match到的pattern取代為str1

4. 利用$1可以取得()中match到的pattern  (一定要用小括號)

e.g. (將2進位數字轉換成number) 

  str.replace(/([0-1]+)/g, "parseInt(\"$1\",2)")
  eval(str)

● test($str)：  (regexp method)
  用來測試string是否包含pattern(回傳true或false)
e.g.

 var res = new RegExp(pattern, modifier);
 var str = "...";
 res.test(str);

● match： (String method)
  用來測試string 是否包含pattern(回傳match的pattern)
e.g.

 var str = "...";
 var res = str.match(/pattern/modifier);

Regular Expression-perl

文章轉
http://user.frdm.info/ckhung/b/re/rules.php
http://ind.ntou.edu.tw/~dada/cgi/Perlsynx.htm


/regular expression/expression modifier
● Modifiers：
  g: Match globally, i.e. find all occurrences. (搜尋全部)

  i: Makes the search case-insensitive. (區分大小寫)

  m: If the string has new-line characters embedded within it, the metacharacters ^ and $ will not work correctly. This modifier tells Perl to treat this line as a multiple line. (包含多行)

  o: Only compile pattern once.

  s: The character . matches any character except a new line. This modifier treats this line as a single line, which allows . to match a new-line character. 

  x: Allows white space in the expression.

● regular expression:
  ○特殊意義字元：
    \  跳脫字元
    ^ 以...為開頭
    . 除了換行的所有字串
    $ 以...為結尾
    | 或
    [] 搜尋誇號中字元
    () 括號

  ○ 字元數量關係：
    * 大於等於0次
    + 大於等於一次
    ? 0或1次
    {n} n次
    {n.} 至少n次
    {n, m} 最少n次，不超過m次

  ○ 特定字元：
    \r: carriage return(CR)
    \n: 換行
    \t: tab
    \w: 英文字母
    \W: 非英文字母
    \s white space
    \S non-white space
    \d: 數字
    \D: 非數字
    \b:  word boundary
    \B: non-word boundary
    \033: octal char
    \x1B: hex char

●

字串比對:

1. $string =~ /regular expression/expression modifier
2. if /regular expression/expression modifier

example:
(將C #define 轉換成verilog #parameter)

###read file
open($fp, "test1.c");
foreach $word (<$fp>)
{
 if ($word=~/^#define (\w+) (\d+)/)
 {
  $word =~ s/define (\w+) (\d+)\n/parameter/g;
  $word = $word . sprintf(" %s = 2'b%b\n",$1 , $2);;
  print "$word";
 }
}
close($fp);

字串取代:

s/PATTERN/REPLACEMENT/egimox

Formal language and automata - ch3

Regular language and regular grammar

Regular expression:

● definition:
 1. 元素：φ, λ, a ∈ Σ 為Regular expression
 2. 運算元：若r₁, r₂為Regular expression
    r₁ + r₂  (union)
    r₁ ⋅ r₂  (concatenation)
    r₁*       (star-closure)
   (r₁)
  均為regular expression
3. 根據有限次數的1和2造出的字串均為regular expression

● language associated with regular expression:

 1. φ is a regular expression {}  (empty set)

 2. λ is a regular expression {λ}

 3. for a ∈ Σ, a is a regular expression denote  {a}

 4. L(r₁ + r₂) = L(r₁) ∪ L(r₂)
 5. L(r₁ ⋅ r₂) = L(r₁)L(r₂)
 6. L((r₁)) = L(r₁)
 7. L(r₁*) = (L(r₁))*

● operation priority:

  star closure > concatenation > union

Regular expression and regular language:

Regular expression -> Regular language

● 所有regular expression 定義的都可以畫成nfa
1. nfa accept φ

2. nfa accept {λ}

3. nfa accept {a}

4. nfa accept L(r₁ + r₂)

5. nfa accept L(r₁ ‧ r₂)

6. nfa accept L((r₁))：直接去掉括號
7. nfa accept (L(r₁))*

Regular language-> Regular expression

● Generalized transition graph(GTG)：一個label為regular expression的transition graph

● nfa轉成complete GTG：將所有沒有連接的edge連上並標上φ
 e.g.

轉換成

● 2 state GTG轉換成regular expression：

r = r₁r₂ (r₄ + r₃r₁*r₂)*

● 3 state(或以上) complete GTG轉換成regular expression：將state減少，直到剩兩個state（initial state和final state）
每次減少state時，考慮將會經過的state，將它加到graph的其他路徑上
e.g.

reduce成：

○完整procedure：
  1. 將nfa轉換成單一final state的GTG，並使它complete
  2. 若GTG state為2，直接代公式
  3. 若GTG state為3，選擇一個要刪除的state(qi)(非final 也非initial的state)
  對於另外兩個state，考慮經過qi的路線
   r1 + r2r3*r4
(均為這種type)
 4. 若GTG大於4，選擇要刪除的state，對所有state均套用 r1 + r2r3*r4找關係
     降為3個state後，再用step3

Regular grammar:

● definition：
 ○left-linear grammar：每次production左側最多只出現1個variable，variable為最左側的symbol
  e.g.：
    A →Bx
    A →x
 ○right-linear grammar：每次production左側最多只出現1個variable，variable為最右側的symbol

 ○regular grammar：left-linear 或 right-linear

 ○linear grammar：每次production左側最多只出現1個variable

● right-linear grammar 轉換成 regular language(nfa)：
  variable → state
  alphabet → state轉換的label

●  regular language轉換成 right-linear grammar：
  δ(q_i, a_j) = q_k 轉換成 q_i → a_jq_k
  (若 q_k 為final state：則轉換成q_k →λ)

● regular language轉換成 left-linear grammar：
  略

● regular expression <=> dfa or nfa <=> regular grammar

  為等價，可以互相轉換

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