マイヒル–ネローデの定理とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > マイヒル–ネローデの定理の意味・解説 

マイヒル–ネローデの定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/10/01 07:50 UTC 版)

ナビゲーションに移動 検索に移動

マイヒル–ネローデの定理: Myhill–Nerode theorem)とは、ある形式言語正規言語であるための必要十分条件を提示した定理である。ほとんどの場合、ある言語が正規言語でないことを証明するのに使われる。

名称は1958年にこの定理を発見したシカゴ大学の John Myhill と Anil Nerode が由来である[1]

定理の内容

ある言語 L について、その文字列についての関係 RL を次のように定義する。すなわち x RL y という関係は、文字列 xzyz のいずれか一方しか L に含まれないというような文字列 z が存在しない。RL が文字列の同値関係であることは容易に示され、従って全ての有限文字列は1つ以上の同値類に分類される。

マイヒル–ネローデの定理は、L を受容する最小オートマトンの状態数が RL の同値類の数と等しいとする。直観的には、そのような最小オートマトンで同じ状態に到達する文字列 xy は、同じ同値類に属することを意味する。そして、文字列群を同値類に分類していけば、同値類毎に状態を設定することで容易にオートマトンを構築できる。

結論と利用

マイヒル–ネローデの定理の結論は、言語 L が正規言語であること(すなわち有限状態機械で受容されること)と、RL の同値類の個数が有限であることが同値ということになる。

この定理の系として、無限の同値類を定義する言語は正規言語ではないと言える。ある言語が正規言語でないことを証明するのに使われるのは、この系である。

例えば、3で割り切れる2進数からなる言語は正規言語である。3で割ったときの余りは、0、1、2 の 3種類あるので、3つの同値類が存在する。従って、その言語を受容する最小オートマトンは、それぞれの同値類に対応した3つの状態を持つことになる。

脚注

  1. ^ A. Nerode, "Linear automaton transformations", Proceedings of the AMS, 9 (1958) pp 541-544.

参考文献

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  
  •  マイヒル–ネローデの定理のページへのリンク

辞書ショートカット

すべての辞書の索引

「マイヒル–ネローデの定理」の関連用語

マイヒル–ネローデの定理のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



マイヒル–ネローデの定理のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのマイヒル–ネローデの定理 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS