形式言語
(この2つの違いは、一部の入力に対してチューリングマシンが停止しない場合があるかどうかである) また、チューリングマシンTMの言語 L(TM) とは、テープに w をセットしたあと、TMを動作させると受理状態に入って停止するような w の集合からなる言語(TM認識可能な言語)のことである。
この言語には以下のような演算が定義される。ここで、 L 1 {\displaystyle L_{1}} と L 2 {\displaystyle L_{2}} は共通のアルファベットから構成される言語であるとする。
「連結」 L 1 L 2 {\displaystyle L_{1}L_{2}\quad } は、文字列群 v w {\displaystyle vw} から構成される。ここで、 v {\displaystyle v} は L 1 {\displaystyle L_{1}} に含まれる文字列で、 w {\displaystyle w} は L 2 {\displaystyle L_{2}} に含まれる文字列である。
「積集合」 L 1 ∩ L 2 {\displaystyle L_{1}\cap L_{2}} は、 L 1 {\displaystyle L_{1}} にも L 2 {\displaystyle L_{2}} にも含まれる文字列の集合である。
「和集合」 L 1 ∪ L 2 {\displaystyle L_{1}\cup L_{2}} は、 L 1 {\displaystyle L_{1}} か L 2 {\displaystyle L_{2}} に含まれる文字列の集合である。