オートマトン・形式言語及び演習
— 1. 有限オートマトンとは—
酒井 正彦
www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/
1- 1 / 27
形式言語
言語とは：文字列の集合
例：偶数個の1の後に0を持つ列からなる集合
{0, 110, 11110, · · · }
形式言語:数学モデルに基づいて定義された言語
認識機械:文字列が該当言語に属するか？
機械
文字列 受理/非受理
文法:規則により該当言語に属する文字列を生成
規則の例：
S → 11S | 0
生成の例：
S ⇒ 11S ⇒ 1111S ⇒ 11110
1- 2 / 27
言語のクラス
言語を定義する数学モデル（上の方がクラスが広い）
言語の名称 文法 認識機械
帰納的可算 (制限なし) チューリング機械
... ... ...
文脈自由 文脈自由 プッシュダウン
・オートマトン
正規 正規 有限オートマトン
... ... ...
1- 3 / 27
有限オートマトン
状態をもつシステムに応用
- ディジタル回路の動作設計
- コンパイラの字句解析
- ＷＥＢなどのテキストからのキーワード検索
- 通信プロトコルなどの有限状態システムの検査
有限オートマトン
例：オン・オフ切り替えスイッチ
例：文字列thenの認識
基礎的概念
アルファベット：記号の空でない有限集合
- 例：Σ ={0, 1} 2進アルファベット
- 例：Σ =
{a, b, · · · , z} すべての小文字の集合
文字列：アルファベット中の記号の有限列
- 例えば、01101
空列：0個の記号からなる文字列
- εで表す
基礎的概念
列の長さ： 記号の出現の数
-
wの長さを
|w|で表す
- 例：|011| = 3 |ε| = 0
アルファベットのベキ：Σ
kはΣから作られる長さ
kの列の
集合
- 例：Σ ={0, 1}
Σ1
={0, 1}
Σ2
={00, 01, 10, 11}
Σ0
={ε}
- 質問：Σ3
の要素数は？
1- 7 / 27
基礎的概念
Σ上の全ての列の集合Σ∗
：
Σ∗
= Σ0
∪ Σ1
∪ Σ2
∪ · · ·
また、
Σ+
= Σ1
∪ Σ2
∪ Σ3
∪ · · ·
Σ∗
= Σ+
∪ {ε}
連接：
xと
yを文字列とするとき、
xyは
xが表す文字列の
後に
yが表す文字列をつないで得られる文字列を表す
x = a1
a2
· · · aiy = b1
b2
· · · bj
xy = a1
a2
· · · aib1
b2
· · · bj
- 例：
x = 01101 y = 110 xy = 01101110
- 任意の列
xについて、
xε = εx = xが成り立つ
1- 8 / 27
基礎的概念
言語：
L ⊆ Σ∗
のとき、Lを(Σ上の)言語という
言語の例：
- 英単語の集合
- Cプログラムの集合
- いくつかの0のあとに同数個の1が並んだ列からなる
集合
{ε, 01, 0011, 000111, · · · }
- 0と1が同じ数だけ含まれている列の集合
{ε, 01, 10, 0011, 0101.1001, · · · }
1- 9 / 27
基礎的概念
言語の例(続き)：
- 素数を表す2進数の集合
Lp={10, 11, 101, 111, 1011, · · · }
- 空集合∅
- 空列だけからなる集合{ε}
注意：∅ 6= {ε}
注意：アルファベットΣは有限集合(言語は無限集合も
扱う)
決定性有限オートマトン
決定性有限オートマトン(DFA)は、次の5項組
A = (Q, Σ, δ, q0,
F)
-
Q：状態の有限集合
- Σ：有限のアルファベット(入力記号の有限集合)
- δ：遷移関数(
q, a) 7→ p
-
q0
∈ Q：開始状態
-
F ⊆ Q：最終状態(あるいは、受理状態)の集合
決定性有限オートマトン
例：
L = {x01y | x, y ∈ {0, 1}∗
}を認識するオートマトンA
-
A = ({q0,
q1,
q2
}, {0, 1}, δ, q0,
{q1})
- 遷移表
- 遷移図
決定性有限オートマトン
有限オートマトンが文字列
w = a1
a2
· · · anを受理する：
遷移図に以下を満たすパス(経路)が存在するとき
- 開始状態で始まる
- 最終状態で終る
- ラベルの列が
a1
a2
· · · an
例：先の有限オートマトン
は、文字列01101を受理する
1- 13 / 27
決定性有限オートマトン
遷移関数δ(引数:状態と文字、返値:状態)をδ(引数:状態と文
字列、返値:状態)に拡張
(x ∈ Σ∗
, a ∈ Σ)
基底：δ(
q, ε) = q
帰納：δ(
q, xa) = δ(δ(q, x), a)
受理の形式な定義
Aが
wを受理
: δ(q0,
w) ∈ F
Aが認識する言語
: L(A) = {w | δ(q0,
w) ∈ F}
オートマトンで認識できる言語(それを認識するオートマト
ンが存在する言語)を正則言語(あるいは、正規言語)という
1- 14 / 27
決定性有限オートマトン
例：0と1の出現がそれぞれ偶数回の文字列を受理するDFA
1- 15 / 27
DFA の性質の例と証明
以下で定義される
DFA Aは、
L(A) = {w | |w|が奇数}を満
たす
0
q
1
1
q
1
(1)と(2)が共に成り立つことを
wの長さに関する帰納法で
証明する
(1) δ(
q0,
w) = q0ならば
|w|は偶数、その逆も成立
(2) δ(
q0,
w) = q1ならば
|w|は奇数、その逆も成立
性質の証明
基底：
|w| = 0のとき、w = εより明らか
帰納：
|w| > 0のとき、
w = v1 (v ∈ Σ∗
)と書ける
(1) (右向きの証明)
δ(
q0,
v1) = q0とする。このとき、
δ(
q0,
v1) = δ(δ(q0,
v), 1)よりδ(
q0,
v) = q1
帰納法の仮定(2)より、
|v|は奇数
よって
|w|は偶数
(左向きの証明)
|w|は偶数とすると、
|v|は奇数
帰納法の仮定(2)より、δ(
q0,
v) = q1であるから、
δ(
q0,
v1) = δ(δ(q0,
v), 1) = δ(q1, 1) =
q0
(2) (1)と同様に示せる
DFA の例
例：教科書p.58問2.2.1
DFA の例
前ページの例を表現するDFA
状態を3ビット列の後ろ
にa(accepted)かr
(rejected)をつけて表す
前回の入力の際にDに落
ちればa、それ以外ならr
とする
図の開始状態は000r
A B
→ 000r 100r 011r
∗000a 100r 011r
∗001a 101r 000a
010r 110r 001a
∗010a 110r 001a
011r 111r 010a
100r 010r 111r
∗100a 010r 111r
101r 011r 100a
∗101a 011r 100a
110r 000a 101a
∗110a 000a 101a
111r 001a 110a
1- 19 / 27
非決定性有限オートマトン
非決定性のオートマトンの遷移先は状態の集合
例：01で終る系列を受理する非決定性有限オートマトン
00101を入力したときの動作
1- 20 / 27
非決定性有限オートマトン
非決定性有限オートマトン(NFA)の定義
A = (Q, Σ, δ, q0,
F)
-
Q：状態の有限集合
- Σ：有限のアルファベット
- δ：遷移関数(
q, a) 7→ {p1,
· · · , pn}
-
q0
∈ Q：開始状態
-
F ⊆ Q：最終状態(あるいは、受理状態)の集合
1- 21 / 27
非決定性有限オートマトン
例：先程のNFA
({q0,
q1,
q2
}, {0, 1}, δ, q0,
{q2})
ここでδは次の遷移関数
非決定性有限オートマトン
遷移関数の拡張
(x ∈ Σ∗
, a ∈ Σ)
- 基底：δ(
q, ε) = {q}
- 帰納：δ(
q, xa) = [
p∈δ(q,x)
δ(
p, a)
例：δ(
q0, 00101)を計算しよう。
定義
Aが
wを受理する：
δ(
q0,
w) ∩ F 6= ∅
Aが認識する言語：
L(A) = {w | δ(q0,
w) ∩ F 6= ∅}
NFA の性質の例と証明
次のNFAは
L = {w01 | w ∈ Σ∗
}を認識する
次の三つの性質が任意の
w ∈ Σ∗
について成り立つことを同
時帰納法により証明する
(1)
q0
∈ δ(q0,
w)
(2)
q1
∈ δ(q0,
w)ならば
wは0で終り、その逆も成立する
(3)
q2
∈ δ(q0,
w)ならば
wは01で終り、その逆も成立する
性質の証明
基底：
|w| = 0のとき、(1)は明らか。(2)と(3)は両辺が共
に偽となり、成立
帰納：
w = xaのとき、
(1) δ(
q0,
xa) =
[
p∈δ(q0,
x)
δ(
p, a)
帰納法の仮定(1)より、q0
∈ δ(q0,
x)
よって
aが0と1のいずれの場合も
q0
∈ δ(q0,
a)である
ことから、成立
1- 25 / 27
性質の証明
帰納(続き)：
w = xaのとき、
(2) (右向きの証明)
q1
∈ δ(q0,
xa)とする
このとき、
q1∈
[
p∈δ(q0,
x)
δ(
p, a)であることから、
a = 0
(左向きの証明)
a = 0とする
帰納法の仮定(1)より、
q0
∈ δ(q0,
x)
これと、
q1
∈ δ(q0, 0)から、
q1
∈ δ(q0,
x0)
1- 26 / 27
性質の証明
帰納(続き)：
w = xaのとき、
(3) (右向きの証明)
q2
∈ δ(q0,
xa)とする
このとき、q2∈
[
p∈δ(q0,
x)
δ(
p, a)であることから、p = q1
かつ
a = 1
よって、帰納法の仮定(2)より、
xは0で終る
(左向きの証明)
xが0で終り、a = 1とする
帰納法の仮定(2)より、
q1
∈ δ(q0,
x)
これと、
q2
∈ δ(q1, 1)から、
q2
∈ δ(q0,
x1)
1- 27 / 27
