|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 定理 ： [ていり] 【名詞】 1. theorem 2. proposition ・ 理 ： [り] 【名詞】 1. reason
マイヒル–ネローデの定理（英: 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）』 ■ウィキペディアで「マイヒル–ネローデの定理」の詳細全文を読む スポンサード リンク
|