計算理論の基礎(正規言語) part1

[計算理論]正規言語

計算モデルの導入

理想的な計算モデルとして有限状態機械「有限オートマトン」を導入する。

・有限オートマトンの正式な定義
有限オートマトンは以下の要素を持つ。

  • 状態の集合
  • 入力アルファベット
  • 動作規則(δ:遷移関数 によって定義される)
  • 開始状態
  • 受理状態

状態遷移関数の定義
状態xから状態yへ入力1によって遷移する関数を
δ(x, 1) = y
と定義する。

よって、有限オートマトン(finite automaton)は5個組(Q,Σ,δ,q0,F)から成り立つ。
\[ 1. Qは状態(state)と呼ばれる有限集合 \]
\[ 2. Σ はアルファベット(alphabet)と呼ばれる有限集合 \]
\[ 3. δ: Q \times Σ \rightarrow Q は遷移関数 \]
\[ 4. q_0 \in Q は開始状態 \]
\[ 5. F \subseteq Qは受理状態の集合 \]

受理・認識する

機械Mの言語:Aが機械Mを受理するすべての文字列の集合であるならば、Aは機械Mの言語という。
L(M) = A は「MはAを認識する(受理する)」を意味する。
(Aが言語である場合は「認識」を使う)

機械は複数の文字列を受理するが、つねに唯一の言語を認識する。必ず空言語を認識する。

有限オートマトンの計算の正式な定義

M=(Q, Σ, δ, q0, F)を有限オートマトンとし、
ω = ω1 ω2 ω3 ...ωn は文字列で各ωiはアルファベットΣの要素とする。
以下の三条件を満たす状態の列、r0,r1,...,rn が存在するならばMはωを受理する。
\[1. r_0 = q_0 (機械が開始状態から始動する) \]
\[2. i = 0, ..., n-1 のとき、δ(r_i, w_{i+1} ) = r_{i+1} (δにより別の状態へ移動する) \]
\[3. r_n \in F (機械が受理状態で終わる) \]

Mが言語Aを認識するのは、A = {ω|Mはωを受理する}

ある有限オートマトンで認識される言語を「正規言語」という。