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!

http://regexvisualizer.apphb.com/

Converting a DFA to a Minimal State DFA

http://jflap.org/tutorial/fa/dfa2mindfa/index.html