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

• 不可區分是一種等價關係，具有等價關係的性質。
• 從DFA的角度來看，不可區分就是兩個不同字串xz和yz進入機器M時，最後都會停在同一個狀態。

• 如果一個語言L是正則的話，則$\equiv_L$的等價類數目是有限的(若且唯若)。
• 接受語言L的最小自動機中狀態的數目等於在$\equiv_L$中等價類的數目。

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.

[例題]  證明 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