結論と利用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/10/01 07:50 UTC 版)
「マイヒル–ネローデの定理」の記事における「結論と利用」の解説
マイヒル–ネローデの定理の結論は、言語 L が正規言語であること（すなわち有限状態機械で受容されること）と、RL の同値類の個数が有限であることが同値ということになる。 この定理の系として、無限の同値類を定義する言語は正規言語ではないと言える。ある言語が正規言語でないことを証明するのに使われるのは、この系である。 例えば、3で割り切れる2進数からなる言語は正規言語である。3で割ったときの余りは、0、1、2 の 3種類あるので、3つの同値類が存在する。従って、その言語を受容する最小オートマトンは、それぞれの同値類に対応した3つの状態を持つことになる。
※この「結論と利用」の解説は、「マイヒル–ネローデの定理」の解説の一部です。
「結論と利用」を含む「マイヒル–ネローデの定理」の記事については、「マイヒル–ネローデの定理」の概要を参照ください。
ウィキペディア小見出し辞書の「結論と利用」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 結論と利用のページへのリンク
