計算理論（その03/X） - 「大人の教養・知識・気付き」を伸ばすブログ

はじめに

Introduction to the Theory of Computation

作者:Sipser, Michael
Course Technology Inc

Amazon

を参照しつつ計算理論を学んでいきます。

前回

power-of-awareness.com

はじめに
前回
1.　正規言語
- 1.1　有限オートマトン
  - 1.1.3　有限オートマトンの設計
  - 1.1.4　正規言語における演算
次回

1.　正規言語

　計算理論はまず「コンピュータとは何か」という問いから始まる。手許にあるノートPCなどのパソコンはコンピュータとしてはあまりに複雑すぎるため、理論的には計算モデル( $computational\ model$ )という理想的なコンピュータを用いる。科学で用いるモデルと同様に計算モデルはある面では正確である一方で、別の面では不正確である。したがって注目したい特徴に応じて異なる複数の計算モデルを扱うことにする。

1.1　有限オートマトン

　有限オートマトン( $\mathrm{finite\ automata}$ )は極度に限られたメモリしか持たないコンピュータに良いモデルである。現実における自動ドアのような単純な動作をモデル化するのに利用可能である。

1.1.3　有限オートマトンの設計

　オートマトンに関することであっても芸術に関することであっても、デザインは創造的な過程である。そのためオートマトンのデザインを単純なレシピや公式に帰着させることはできない。しかし様々な種類のオートマトンを設計するときに便利な特定のアプローチがあり得る。すなわちデザインしようとしているコンピュータに自らを入れ込み、その後そのコンピュータのタスクがどのように実行し得るかを知ることである。
　上で述べた「オートマトンとしての読者」メソッドを用いて有限オートマトンをデザインしよう。ある言語が与えられそれを認識するような有限オートマトンをデザインしたいと仮定する。オートマトンを装うのに、入力文字を受け取り、その文字がオートマトンが認識すると想定している言語の集団に含まれるかを決定しなければならない。文字列内の文字1つ1つを把握することになる。各文字の後、以上で把握したその文字列が言語の中に存在するかを決定しなければならない。その理由は、機械のように、読者が文字列の終端が来たのかを知らないからで、常に答えを用意しなければならない。
　まずこうした決定を行なうためには、文字列を読み込んでいるときにその文字列について何を記録する必要があるかを理解しなければならない。単純に認識したものをすべて記録してはどうだろうか。覚えておくべきなのは、有限オートマトンを装うをしていることおよびこの種のコンピュータはわずか有限の数の状態、すなわち有限のメモリしか持っていないことである。入力が極端に長い―たとえばここから月まで―場合を考えてみれば、恐らくそのすべてを記憶することはできないだろう。限られたストレージ容量しかもたない―たとえば1枚の紙相当—ような有限のメモリしか持っていない。幸いにも、多くの言語においてすべての入力を記録する必要はない。特定の重要な情報のみ記録すればよい。まさにどの情報が重要なのかは想定している特定の言語次第である。

　たとえばアルファベットが $\{0,1\}$ で言語が奇数個の $1$ を持つすべての文字列だとする。そしてこの言語を認識する有限オートマトン $E_1$ を構築したいとする。オートマトンのふりをすべく、 $0,1$ からなる入力文字列を1文字ずつ取得する。 $1$ の個数が奇数であるか否かを決定するために全文字列を記録する必要はあるか。もちろん、そんなことはない。単純にそれまでの $1$ の個数が偶数か奇数かを記録し、そして新しい文字を読み込んだ際にこの情報を残しておけばよい。もし $1$ を読み込めば答えを返しせばよい。しかしもし $0$ を読み込めば、答えはそのままにしておけばよい。
　しかし $E_1$ のデザインにこれがどのように役立つのか。ひとたび読み込まれるがままに文字列を覚えるように必要な情報を決定していれば、この情報は確率の有限なリストとして表示される。この例では、確率はとりあえず偶数もしくはとりあえず奇数となる。すると各確率にある状態を割り当てることになる。これらがここで示す $E_1$ の状態である。

2つの状態 $\boldsymbol{q_{\mathrm{even}}}$ と $\boldsymbol{q_{\mathrm{odd}}}$

　次に、記号を読み込むことである確率が別の確率に移る方法を見ることで遷移を配置する。したがって、もし状態 $q_{\mathrm{even}}$ が偶数である確率を表し状態 $q_{\mathrm{odd}}$ が奇数である確率を表すならば、状態を変える遷移を $1$ で、状態を維持する遷移を $0$ で表すことになる。

確率の配置された遷移図

　そして、 $0$ 文字(空文字列 $\varepsilon$ )を読み込んだことに関連した確率に対応する状態である開始状態を設定する。この事例では、 $0$ は偶数だから開始状態は $q_{\mathrm{even}}$ である。最後に、入力した文字列を強したい確率に対応する許容状態を設定する。ここでは $1s$ の奇数番号を認識したときに許容したとしたいから、[tex:q_{\mathrm{odd}}を許容状態とする。

開始状態と許容状態を追加した遷移図

1.1.4　正規言語における演算

　有限オートマトンおよび正則言語の性質を調べていく。そうすることで特定の言語を認識するためのオートマトンをデザインするための技術を開発できる。
　算数において基本的な対象は数であり、道具は数を操作するための $+$ や $\times$ といった演算子である。計算理論では対象が言語であり、道具はそれらを操作するために特別にデザインされた演算子である。ここで正規演算( $regular\ operation$ )と呼ばれる、言語に対する3つの演算子を定義し、これらを正規言語の性質を調べるために用いる。

定義1.4　正規演算　 $A,B$ を言語とする。正規演算として和( $union$ )、連結( $concatenation$ )およびスター( $star$ )を以下で定義する。

和( $union$ )：
　 $A\cup B=\left\{x\left|\right.x\in A\lor x\in B\right\}$
連結( $concatenation$ )：
　 $A\circ B=\left\{xy\left|\right. x\in A\land y\in B\right\}$
スター( $star$ )：
　 $A^{*}=\left\{x_1x_2\cdots x_k\left|\right.k\geq0\land x_i\in A\right\}$

　連結演算は、新しい言語の文字列を得るべく想定できるあらゆる方法で $B$ に含まれる文字の前に $A$ に含まれる文字を充てる。
　スター演算は、2つの異なる言語というよりは1つの言語に適用されるという点で他2つとは少し異なる演算である。すなわちスター演算は1項演算である。スター演算は新たな言語を得るべく、 $A$ に含まれる任意の数の文字列を結合する。任意の数とは $0$ を含み、空文字列 $\varepsilon$ は $A$ が何であれ常に $A^{*}$ に含まれる。

定理1.5　正規言語のクラス　正規言語のクラスは和演算に関して閉じている。すなわち $A_1,A_2$ が正規言語であるならば、 $A_1\cup A_2$ もまた正規言語である。

( $\because$ 　 $M_1=\left(Q_1,\Sigma,\delta_1,q_1,F_1\right)$ )として $M_1$ は $A_1$ を認識し、 $M_2=\left(Q_2,\Sigma,\delta_2,q_2,F_2\right)$ )として $M_2$ は $A_2$ を認識するものとする。 $M=\left(Q,\Sigma,\delta,q_1,F\right)$ に対して $A_1\cup A_2$ を認識する $M$ を以下を満たすように構築する。

$Q=Q_1\times Q_2=\left\{(r_1,r_2)\left|\right.r_1\in Q_1 \land r_2\in Q_2\right\}$
$\Sigma$ は $M_1,M_2$ に共通とする。
遷移関数 $\delta$ を以下のように定義する。
　 $(r_1,r_2)\in Q,$ $a\in\Sigma$ に対して
$\begin{aligned}\delta\left((r_1,r_2),a\right)=\left(\delta(r_1,a),\delta(r_2,a)\right)\end{aligned}$
とおく。
$q_0=(q_1,q_2)$ とする。
$F$ はその一方が $M_1,M_2$ の許容状態であるような状態の組の集合とする。