正規言語とは何か？

正規言語とは

正規言語とは、ある有限オートマトンで認識される言語を指します。
この、有限オートマトン、認識する、についてを今回は説明することで正規言語とは何かを紐解いていこうと思います。

有限オートマトン

• 有限オートマトンを簡単に説明するなら、計算機の構造や動作を抽象化したモデルです。
• ある内部機構を持った「装置」で初期の「状態」を持っており、外部からの「操作」が行われた時、その「操作」がその「装置」に受け入れられるならその「操作」に応じた「状態」を返します。

有限オートマトンの抽象的記述

• 下記は3つの状態を持つ有限オートマトンM₁を表している。

[3つの状態を持つ有限オートマトンM₁の説明]

• 上の図をM₁の状態遷移図と呼びます。
• M₁は、3つの状態である、 q1, q2, q3 を持っています。

[3つの状態の詳細]

• q1は、開始状態を表します。何もない場所からの矢印で示されています。
• q2は、受理状態を表します。これは、二重の円で示されています。
• 状態から状態への矢印は遷移と呼びます。

[オートマトンの出力]

• 受理または拒否のどちらかです。

[M₁への入力と動作例]
入力値を10101とします。

① 状態q1から動き出します。
② 1を読み出し、q1からq2へ遷移します。
③ 0を読み出し、q2からq3へ遷移します。
④ 1を読み出し、q3からq2へ遷移します。
⑤ 0を読み出し、q2からq3へ遷移します。
⑥ 1を読み出し、q3からq2へ遷移します。
⑦ 入力を読み終えた時にM₁は、受理状態q2にあるので受理します。

数学的側面から有限オートマトンについて考えてみる

• 有限オートマトンは、5個組みのもののリストである。

1 : Q は状態と呼ばれる有限集合 \\
2 : \sum はアルファベットと呼ばれる有限集合 \\
3 : \delta はアルファベットと呼ばれる有限集合 \\
4 : q_0 \in Q　は開始状態 \\
5 : F \subseteq は受理状態の集合

• 遷移状態関数とは、有限オートマトンにおいて状態aから状態bへ文字１をラベルとして持つ矢印がある場合、それはオートマトンが状態aに1が読み出された時に状態bへ移ることを指します。
• 数式だと下記のようになる。

\delta (a,1) = b

• この定義に、先ほどの図の有限オートマトンM₁を当てはめていくと下記のようになる。
  

• ここで最初の正規言語に戻ってくる。

• ある集合(すべて文字列)を受理する機械Mがあるとすると、Aは機械Mの言語である、もしくは機械MはAを受理する、もしくは、機械MはAを認識するという。

• つまり、正規言語とは、ある有限オートマトンで認識される言語 = 機械Mが受理するようなある集合(すべて文字列)と言い換えることができると思います。

参考文献

計算理論の基礎 [原著第2版]