Aritalab:Lecture/Automata/Intro

Revision as of 11:58, 7 May 2012

準備

アルファベット

記号の有限集合をアルファベットと言います。アルファベット Σ 上の列とは、記号を重複を許して並べたものです。例えば Σ = {0,1} なら 001010 は長さ 6 の列です。 長さ 0 の列を ε で表わします。 列 x の逆とは x を後ろから逆に読んだもので、 x^R と書きます。二つの列 x, y の連接を xy と書きます。 同じ列の連接は x² のように書くときもあります。 列の 0 個以上の連接によりできる集合を Σ^* と書きます。（スター演算と呼びます。） このとき、0　個の連接でもよいから ε ∈ Σ^* です。 列 x の一部を部分列といいます。正確には列 w が w = xyz と書けるとき y を w の部分列といい、このとき、x, z は ε でもよいとします。

言語

アルファベット Σ 上の言語とは Σ 上の、列の有限、または無限集合のことです。例えば

{0ⁿ1ⁿ | n ≥ 0}

は 0, 1 が正確に同じ数だけ繰り返される列の全体からなる言語です。空集合も言語であり、特別に Φ と書きます。言語と言語の連接は

L₁L₂ = { x₁x₂ | x₁ ∈ L₁, x₂ ∈ L₂ }

と定義します。言語のスター演算も同様に定義します。

例. (xy)^R = y^Rx^R

帰納法により証明します。　|xy| = 0 のとき、x = y = ε なので成立します。　|xy| = k (k ≥ 0) のとき、命題が正しいと仮定します。　

• x = ε のとき

命題は自明です。

• x = ax' と書けるとき

(xy)^R = (ax'y)^R = (x'y)^Ra = y^Rx'^Ra = y^Rx^R

よって命題は成立します。

例. 任意の言語 L と空集合 Φ において LΦ = Φ

Φ は空集合なので、これに含まれる列はありません。連接を作っても空集合です。

例. 任意の言語 L と空文字 ε において Lε = L

L に含まれる任意の列 x において xε = x が成立します。

例. 回文

条件 x = x^R を満たすものを回文といいます。回文は以下のように帰納的に定義できます。

• ε またはアルファベット1文字からなる列は回文である。
• x が回文のとき、アルファベット1文字からなる任意のyについて yxy は回文である。