2015年4月29日 星期三

Formal Language - Ch5 邁希爾-尼羅德定理 Myhill-Nerode Theorem

 

不可區分 (Indistinguishable) 
給定一個語言$L$和兩個字串$x,y$,如果所有 $z \in Σ^*$ 要麼同時$xz,yz$在$L$中,要麼同時$xz,yz$不在$L$中,則稱$x,y$不可被$L$所區分(indistinguishable),寫做$x \equiv_L y$。
  • 不可區分是一種等價關係,具有等價關係的性質。
  • 從DFA的角度來看,不可區分就是兩個不同字串xz和yz進入機器M時,最後都會停在同一個狀態。



邁希爾-尼羅德定理 (Myhill-Nerode Theorem)
  • 如果一個語言L是正則的話,則$\equiv_L$的等價類數目是有限的(若且唯若)。
  • 接受語言L的最小自動機中狀態的數目等於在$\equiv_L$中等價類的數目。

根據第一點可以推知,如果一個語言定義等價類的無限集合,它就不是正則的。這個推論經常被用來證明一個語言不是正則的。

例如,由可以被 3 整除的二進位數組成的語言是正則的。有三個等價類 3 - 被 3 除的時候餘數是 0, 1 和 2 的數。接受這個語言的極小自動機有對應於等價類的三個狀態。



邁希爾-尼羅德定理用法
  1. Given a langauge B, construct the equivalence relation B by using B.
  2. Prove that B has finite or infinite index:
    • Finite: B is a regular language.
    • Infinite: B is not a regular language.

補記 : Myhill-Nerode Theorem比pumping lemma好用,檢驗充要條件完,如果是正則語言直接得到最小自動機,有了這個 pumping lemma for regular expression 可以說完全被取代。


[例題]  證明 nonregular
$A = {0^n1^n: n ≥ 0}$ is not regular.
Proof : Consider the sequence of strings $x_1, x_2, \dots$ where $x_i = 0^i$ for $i ≥ 1$. We now see that no two of these are equivalent to each other with respect to $≡A$: Consider $x_i = 0^i$ and $x_j = 0^j$ for $i \neq j$. Let $z = 1^i$ and notice that $x_iz = 0^i1^i \in A$ but $x_jz = 0^j1^i \notin A$. Therefore no two of these strings are equivalent to each other and thus A cannot be regular.



Minimizing DFAs - Table-filling Algorithm
  1. Basis : If $p \in F$ and $q \notin F$, ${p,q}$ is distinguishable.
  2. Induction step : If a string $w$ distinguishes two states $p$ and $q$, and there exist states $r$ and $s$ with $δ(p, a) = r$ and $δ(q, a) = s$, then the string $aw$ distinguishes $r$ and $s$.

[例題]  最小自動機化減





Reference

交大陳穎平教授正規語言講義

Regular expression visualizer  -  這個工具很有趣,可以把RE直接轉成DFA和NFA!

Converting a DFA to a Minimal State DFA
http://jflap.org/tutorial/fa/dfa2mindfa/index.html





技術提供:Blogger.