第１２回：253pdf 最近の更新履歴 Hideo Fujiwara

前回までの復習

有限オートマトンが受理する言語（記号列の集合）

        正規言語（正規集合） →  正規表現

(a)

(b)

0 0 1

0 ^{0, 1}

{ 0, 10 }  0 + 10

0(0+1)^*

{ 0, 00, 01, 000, 001, 010, 011, …}

６９ページ

q₀₀ q_f0 φ

ε ^q0f

q₀ ^a q_f a

空集合

長さ０

入力記号

７０ページ

７０ページ

q₀₀ ⁰ q_f0

q₀₁ ¹ q_f1 0

１

q₀₀ ⁰ q_f0

q₀₁ ¹ q_f1

q_{0 q}

f

ε

ε ε

０＋１

ε

７０ページ

q₀₀ ⁰ q_f0

q₀₁ ¹ q_f1 0

１

q₀ q_f 0

1

q₀ ^{0, 1} q_f q₀₀ ⁰ q_f0

q₀₁ ¹ q_f1

q_{0 q}

f

ε

ε ε

０＋１

ε

７０ページ

７０ページ

q₀₀ ⁰ q_f0

q₀₁ ¹ q_f1 0

１

q₀₀ ⁰ q_{f0 q}

01 ^qf1

1

q_{0 q}

f

ε

０・１

ε ε

q_{0 q}

f

0 ₁

７０ページ

７０ページ

q₀₀ ⁰ q_f0 0

q₀₀ ⁰ q_f0 0^＊

q₀

ε ε

７０ページ

q₀₀ ⁰ q_f0 0

q₀₀ ⁰ q_f0 0^＊

q₀

ε ε

q₀

0

７１ページ

０

＊

０+1

(^０+1)^*

７１ページ

７１ページ

７１ページ

７１ページ

７１ページ