形式言語形式言語の概要

定義

形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列（語 word）の集合である^[1]。

$L\subset \Sigma ^{*}=\{\langle \sigma _{1},\sigma _{2},...\rangle |\sigma _{i}\in \Sigma \}$

ただし、長さゼロの空単語（Empty Word, 記号 $e$ 、 $\epsilon$ 、 $\Lambda$ ）も含む。チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化(エンコード)し、その数値を解釈するプログラムを埋め込む必要がある。チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。

あるチューリングマシンが存在して、言語に属するすべての語 w に対して動作させると受理状態で停止し、属さない語には受理しないようなとき、その言語はチューリング認識可能という。また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。(この2つの違いは、一部の入力に対してチューリングマシンが停止しない場合があるかどうかである) また、チューリングマシンTMの言語 L(TM) とは、テープに w をセットしたあと、TMを動作させると受理状態に入って停止するような w の集合からなる言語(TM認識可能な言語)のことである。

この言語には以下のような演算が定義される。ここで、 $L_{1}$ と $L_{2}$ は共通のアルファベットから構成される言語であるとする。

「連結」 $L_{1}L_{2}\quad$ は、文字列群 $vw$ から構成される。ここで、 $v$ は $L_{1}$ に含まれる文字列で、 $w$ は $L_{2}$ に含まれる文字列である。
「積集合」 $L_{1}\cap L_{2}$ は、 $L_{1}$ にも $L_{2}$ にも含まれる文字列の集合である。
「和集合」 $L_{1}\cup L_{2}$ は、 $L_{1}$ か $L_{2}$ に含まれる文字列の集合である。
$L_{1}$ の「補集合」は、 $L_{1}$ に含まれない全ての文字列の集合である。
「商集合」 $L_{1}/L_{2}\quad$ は、 $L_{1}$ に含まれる文字列 $vw$ に対して、 $L_{2}$ に含まれる文字列 $w$ が存在するときに、全ての $v$ に相当する文字列群から構成される。
「クリーネスター」 $L_{1}^{*}$ は、 $w_{1}w_{2}...w_{n}$ という形式の全文字列群から構成される。ただし、 $w_{i}$ は $L_{1}$ に含まれ、 $n\geq 0$ である。注意すべきは、 $n=0$ の場合もあるので、空文字列 $\epsilon$ も含まれるという点である。
「反転」 $L_{1}^{R}$ は、 $L_{1}$ の全文字列を反転させた文字列群から構成される。
$L_{1}$ と $L_{2}$ の「シャッフル」とは、 $v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}$ で表される全文字列から構成される。ここで、 $n\geq 1$ で、 $v_{1},...,v_{n}$ を連結した $v_{1}...v_{n}$ は $L_{1}$ に含まれる文字列であり、 $w_{1},...,w_{n}$ を連結した $w_{1}...w_{n}$ は $L_{2}$ に含まれる文字列である。