エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント1件
- 注目コメント
- 新着コメント
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
マイヒル–ネローデの定理 - Wikipedia
マイヒル–ネローデの定理(英: Myhill–Nerode theorem)とは、ある形式言語が正規言語であるための必要... マイヒル–ネローデの定理(英: Myhill–Nerode theorem)とは、ある形式言語が正規言語であるための必要十分条件を提示した定理である。ほとんどの場合、ある言語が正規言語でないことを証明するのに使われる。 名称は1958年にこの定理を発見したシカゴ大学の John Myhill と Anil Nerode が由来である[1]。 定理の内容[編集] ある言語 L について、その文字列についての関係 RL を次のように定義する。すなわち x RL y という関係は、文字列 xz と yz のいずれか一方しか L に含まれないというような文字列 z が存在しない。RL が文字列の同値関係であることは容易に示され、従って全ての有限文字列は1つ以上の同値類に分類される。 マイヒル–ネローデの定理は、L を受容する最小オートマトンの状態数が RL の同値類の数と等しいとする。直観的には、
2013/06/03 リンク