有限状態機械の能力
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/17 08:19 UTC 版)
「計算可能性理論」の記事における「有限状態機械の能力」の解説
有限状態機械が受容する言語のクラスを正規言語と呼び、正規文法で記述される。有限状態機械が持つことができる状態は有限個であるためであり、正規言語でない言語を扱うには無限の状態数を扱える必要がある。 正規言語でない言語の例として、文字 'a' と 'b' から構成され、各文字列に必ず 'a' と 'b' が同数含まれている言語がある。この言語が有限状態機械で認識できない理由を調べるため、まずこの言語を受容するための有限状態機械 M {\displaystyle M} があるとする。 M {\displaystyle M} は n {\displaystyle n} 個の状態を持つとする。ここで、文字列 x {\displaystyle x} が ( n + 1 ) {\displaystyle (n+1)} 個の 'a' の後に ( n + 1 ) {\displaystyle (n+1)} 個の 'b' があるような構成であるとする。 M {\displaystyle M} の状態数は n {\displaystyle n} しかないため、 x {\displaystyle x} を入力としたときに最初の 'a' が連続する部分の長さが ( n + 1 ) {\displaystyle (n+1)} であることから、鳩の巣原理により、何らかの状態を繰り返すことになる。 ( n + 1 ) {\displaystyle (n+1)} 個の 'a' を読み込んだ状態 S {\displaystyle S} が 'a' を d {\displaystyle d} 個読み込んだ時に再度現われるとする（ d > 0 {\displaystyle d>0} とする）。つまり、 ( n + d + 1 ) {\displaystyle (n+d+1)} 個の 'a' を読み込んだときと ( n + 1 ) {\displaystyle (n+1)} 個の 'a' を読み込んだときの状態が区別されない。従って、 M {\displaystyle M} が x {\displaystyle x} を受容するなら、その機械は ( n + d + 1 ) {\displaystyle (n+d+1)} 個の 'a' と ( n + 1 ) {\displaystyle (n+1)} 個の 'b' からなる文字列も受容してしまう。しかしその文字列は 'a' と 'b' が同数でないため、言語の定義からは受容してはいけない文字列なのである。 従って、この言語は有限状態機械では正しく受容できず、正規言語ではないということになる。これを一般化したものを正規言語の反復補題と呼び、各種言語クラスが有限状態機械で認識できないことを示すのに使われる。 この言語を認識できるプログラムは簡単に書けると思われるかもしれない。そして、現在のコンピュータは有限状態機械でモデル化できると上に書いてある。もちろんプログラムは書けるが、この問題の本質はメモリ容量の限界の見極めにある。非常に長い文字列を与えられた場合、コンピュータのメモリ容量が足りなくなって入力文字数を数えられなくなり、オーバーフローするだろう。その意味で、現代のコンピュータは有限状態機械と同じと言える。したがって、この言語の文字列の大部分は認識できるとしても、必ず認識できない文字列が存在する。
※この「有限状態機械の能力」の解説は、「計算可能性理論」の解説の一部です。
「有限状態機械の能力」を含む「計算可能性理論」の記事については、「計算可能性理論」の概要を参照ください。
- 有限状態機械の能力のページへのリンク
