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

  為等價，可以互相轉換