V´azquezらのアルゴリズムの出力の最大状態数についてまとめると，表3.1のようにな
る．表3.1でマスが2段となっているところは，上段が，出力の状態数の最大値を表し，
下段が，出力の状態数が最大となる（現在見つかっている）入力例の，本アルゴリズム 適用時の状態や文字の選択順の指定の有無を表す．
また，V´azquezらのアルゴリズムの出力の最小状態数について，定理7が成り立つ．
定理 7. 入力が任意のNFAであっても，到達可能なDFAを反転したものであっても，
|Σ| ≥1, k ≥1のとき，V´azquezらのアルゴリズムの出力の状態数|Q′|について，|Q′| ≥1 が成り立つ．またこの下界は厳密である．
{0,1,2,3}
{0,1,2,3} 𝑎
{1,2,3}
{4}
𝑎
{0,1,2,3}
{0}
𝑎
{1,2,3}
{4}
𝑎, 𝑏 𝑏
𝑎 𝑎
0 1 2 𝑎 3
𝑎
𝑏 𝑏 𝑏 𝑏
𝑎 4
𝑏
{0,1,2,3}
{0}
𝑎
{1,2,3}
{2,3}
{4}
𝑎
𝑎, 𝑏 𝑎
𝑏
{0,1,2,3}
{0}
𝑎
{1,2,3}
{2,3}
{1}
{4}
𝑎, 𝑏
𝑎, 𝑏 𝑎
𝑏 𝑏
{0,1,2,3}
{0}
𝑎
{1,2,3}
{2,3}
{1}
{4}
𝑎, 𝑏 𝑎, 𝑏
𝑎 𝑎
{3}
𝑎 𝑏
𝑏
{0,1,2,3}
{0}
𝑎
{1,2,3}
{2,3}
{1}
{4}
𝑎, 𝑏 𝑎, 𝑏
𝑎 𝑎
{2} {3}
𝑎, 𝑏 𝑏
𝑏 𝑏
{0,1,2,3}
{0}
𝑎
{1,2,3}
{2,3}
{1}
𝑎
{4}
𝑎, 𝑏 𝑎, 𝑏
𝑎 𝑎 𝑎
{3}
{2}
𝑎 𝑎
𝑎, 𝑏 𝑏 𝑎
𝑏 𝑏
𝑏
𝑏
𝑏 𝑏
𝑏
入力
… 1,2,3 , 𝑎
2,3 , 𝑏 2,3 , 𝑎
1,2,3 , 𝑏
0,1,2,3 , 𝑏 0,1,2,3 , 𝑎
出力
図 3.11: 到達可能なDFAを反転したものを入力とし，|Σ|= 2のとき，V´azquezらのア ルゴリズムの出力の状態数が2k−2となる具体例．
表 3.1: V´azquezらのアルゴリズムの出力の最大状態数
入力Mの 任意の入力M 到達可能なDFAを反転した入力M 状態数k |Σ|= 1 |Σ| ≥2 |Σ| ≥1
1 1 1 1
2≤k ≤5 2k−2 2k−1 2k−2
（選択順指定無）（選択順指定有） （選択順指定無）
k≥6 2k−2 2k−1 2k−2
（選択順指定有）（選択順指定有） （選択順指定有）
図 3.12: |Σ|= 1のとき，V´azquezらのアルゴリズムの出力の状態数が1となる入力例．
証明. |Σ|= 1のとき，V´azquezらのアルゴリズムの出力の状態数が1となる入力例を，図 3.12に示し，このNFAをM1とする．ここで，M1を反転したRev(M1)は，到達可能な DFAである．また，M1に本アルゴリズムを適用する場合の状態の選択順は一意である．
M1に本アルゴリズムを適用すると，M1の状態集合Qが出力の初期状態として求まる．
状態Qから文字aによる遷移先は状態Qであり，新たな状態は生成されない．よって，
アルゴリズムは終了し，出力のNFAはその状態集合Q′ ={Q}，すなわち|Q′| = 1であ るものとなる．
|Σ| = 2のとき，V´azquezらのアルゴリズムの出力の状態数が1となる入力例を，図 3.13に示し，このNFAをM2とする．ここで，M2を反転したRev(M2)は，到達可能な DFAである．また，M2に本アルゴリズムを適用する場合の状態の選択順は一意であり，
文字の選択順は任意とする．
M2に本アルゴリズムを適用すると，M2の状態集合Qが出力の初期状態として求まる．
状態Qから文字aによる遷移先は状態Qであり，新たな状態は生成されない．また，状 態Qから文字bによる遷移先も状態Qであり，新たな状態は生成されない．よって，ア ルゴリズムは終了し，出力のNFAはその状態集合Q′ ={Q}，すなわち|Q′| = 1である ものとなる．
|Σ| ≥3のときは，文字aによる遷移は図3.13のaによる遷移と同じとし，a以外の文 字による遷移は図3.13のbによる遷移と同じとして，同様に証明できる
例 16. |Σ|= 1のとき，V´azquezらのアルゴリズムの出力の状態数が1となる具体例を図 3.14に示す．同様に，|Σ|= 2のとき，V´azquezらのアルゴリズムの出力の状態数が1と なる具体例を図3.15に示す．
図 3.13: |Σ|= 2のとき，V´azquezらのアルゴリズムの出力の状態数が1となる入力例．
{0,1,2,3,4} 0,1,2,3,4 {0,1,2,3,4}
入力
出力
図 3.14: |Σ|= 1のとき，V´azquezらのアルゴリズムの出力の状態数が1となる具体例．
{0,1,2,3,4} {0,1,2,3,4}
0,1,2,3,4 , 𝑎
入力
出力
{0,1,2,3,4}
0,1,2,3,4 , 𝑏
図 3.15: |Σ|= 2のとき，V´azquezらのアルゴリズムの出力の状態数が1となる具体例．