翻訳と辞書 Words near each other ・ マイバッハ・ブルー・ジャスティス ・ マイバッハ・ベータ ・ マイバッハ・ベーター ・ マイバッハ・ボム ・ マイバッハ谷口 ・ マイバッハ谷口Jr. ・ マイバブー ・ マイバラード ・ マイバースデイ ・ マイヒル-ネローデの定理 ・ マイヒル–ネローデの定理 ・ マイヒンゲン ・ マイヒーロー! ・ マイビジョン ・ マイファミリー・ウェディング ・ マイファーム ・ マイフィ ・ マイフェアボーイ ・ マイフェアレディ ・ マイフェイバリッと Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク マイヒル–ネローデの定理 ： ウィキペディア日本語版 マイヒル–ネローデの定理 マイヒル–ネローデの定理（英: Myhill–Nerode theorem）とは、ある形式言語が正規言語であるための必要十分条件を提示した定理である。ほとんどの場合、ある言語が正規言語でないことを証明するのに使われる。 名称は1958年にこの定理を発見したシカゴ大学の John Myhill と Anil Nerode が由来である〔A. Nerode, "Linear automaton transformations", ''Proceedings of the AMS'', 9 (1958) pp 541-544.〕。 == 定理の内容 == ある言語 ''L'' について、その文字列についての関係 ''RL'' を次のように定義する。すなわち ''x RL y'' という関係は、文字列 ''xz'' と ''yz'' のいずれか一方しか ''L'' に含まれないというような文字列 ''z'' が存在しない。''RL'' が文字列の同値関係であることは容易に示され、従って全ての有限文字列は1つ以上の同値類に分類される。 マイヒル–ネローデの定理は、''L'' を受容する最小オートマトンの状態数が ''RL'' の同値類の数と等しいとする。直観的には、そのような最小オートマトンで同じ状態に到達する文字列 ''x'' と ''y'' は、同じ同値類に属することを意味する。そして、文字列群を同値類に分類していけば、同値類毎に状態を設定することで容易にオートマトンを構築できる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「マイヒル–ネローデの定理」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.