第８回：232pdf 最近の更新履歴 Hideo Fujiwara

(1)

５０ページ

ε 長さゼロの入力記号列時間ゼロでの瞬間移動

(2)

５０ページ

ε

… … …

(3)

５０∼５１ページ

(4)

５１ページ

(5)

５１ページ

(6)

５１ページ

(7)

５２ページ

(8)

５２ページ

(9)

５２ページ

(10)

５２ページ

(11)

５２ページ

(12)

５３ページ

(13)

５３ページ

(14)

５３ページ

(15)

５３ページつづき

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

５４ページつづき

(26)

５４ページつづき

(27)

p₀ ⁰

p₀ ¹

ちょっと練習

(28)

p₀ ⁰ p₁

p₀ ¹ p₁ ε1 = 1

(29)

p₀ ⁰ p₁ p₁ ⁰

p₀ ¹ p₁ ^p¹ ¹

(30)

p₀ ⁰ p₁ p₁ ⁰ p₂

p₀ ¹ p₁ ^p¹ ^{1 {p}⁰^{, p}¹^{, p}²^} 1ε = 1

(31)

p₀ ⁰ p₁ p₁ ⁰ p₂

p₀ ¹ p₁ ^p¹ ^{1 {p}⁰^{, p}¹^{, p}²^}

p₂ 1 p₁

(32)

５４ページ

(33)

５４ページ

ε

… … … 等は受理される

(34)

５４ページ

(35)

５５ページ

(36)

５５ページ

ε-動作を含まない非決定性有限オートマトンに変換

q₀ ⁰ q₀

q₀^0ε q₁

q₀^0εεq₂

0ε= 0εε = 0

q₀ ⁰ {q₀,q₁,q₂}

(37)

５５ページ

ε-動作を含まない非決定性有限オートマトンに変換

q₀ ^ε1q₁ q₀^ε1εq₂

ε1 = ε1ε= 1

q₀ ⁰ {q₀,q₁,q₂}

q₀ ¹ {q₁,q₂}

(38)

５５ページ

ε-動作を含まない非決定性有限オートマトンに変換

q₁ ¹ q₁ q₁ ^1εq₂

1ε= 1

q₀ ⁰ {q₀,q₁,q₂}

q₀ ¹ {q₁,q₂}

q₁ ¹ {q₁,q₂}

(39)

５５ページ

ε-動作を含まない非決定性有限オートマトンに変換

ε2 = 2

q₀ ⁰ {q₀,q₁,q₂}

q₀ ¹ {q₁,q₂}

q₁ ¹ {q₁,q₂}

q₁ ^ε2q₂

q₁ ² q₂

(40)

５５ページ

ε-動作を含まない非決定性有限オートマトンに変換

q₀ ⁰ {q₀,q₁,q₂}

q₀ ¹ {q₁,q₂}

q₁ ¹ {q₁,q₂}

q₁ ² q₂

q₂ ² q₂

(41)

５５ページ

ε-動作を含まない非決定性有限オートマトンに変換

q₀ ⁰ {q₀,q₁,q₂}

q₀ ¹ {q₁,q₂}

q₁ ¹ {q₁,q₂}

q₁ ² q₂

q₂ ² q₂

(42)

ε-動作を含む非決定性有限オートマトンを

ε-動作を含まない非決定性有限オートマトンに変換

p₀ ⁰ p₁ p₁ ⁰ p₂

1ε

p₀^ε1 p₁ ^p¹ ^{1 {p}⁰^{, p}¹^}

p₂ 1 p₁

p₂

(43)

p₀ ⁰ p₁ p₁ ⁰ p₂

p₀ ¹ p₁ ^p¹ ^{1 {p}⁰^{, p}¹^{, p}²^}

p₂ 1 p₁

ε-動作を含む非決定性有限オートマトンを

ε-動作を含まない非決定性有限オートマトンに変換

p₀ ⁰ p₁ p₁ ⁰ p₂

1ε

p₀^ε1 p₁ ^p¹ ^{1 {p}⁰^{, p}¹^}

p₂ 1 p₁

p₂

ε1 ^{= 1} ε = 1

(44)

p₀ ⁰ p₁ p₁ ⁰ p₂

p₀ ¹ p₁ ^p¹ ^{1 {p}⁰^{, p}¹^{, p}²^}

p₂ 1 p₁

ε-動作を含む非決定性有限オートマトンを

ε-動作を含まない非決定性有限オートマトンに変換

p

₀

_p

1

^p

²

第８回：232pdf 最近の更新履歴 Hideo Fujiwara

ε

… … …

ちょっと 練習

ε

… … … 等は 受理される

ε-動作を含まない非決定性有限オートマトンに変換

ε-動作を含まない非決定性有限オートマトンに変換

ε-動作を含まない非決定性有限オートマトンに変換

ε-動作を含まない非決定性有限オートマトンに変換

ε-動作を含まない非決定性有限オートマトンに変換

ε-動作を含まない非決定性有限オートマトンに変換

ε-動作を含む非決定性有限オートマトンを

ε-動作を含まない非決定性有限オートマトンに変換

ε-動作を含む非決定性有限オートマトンを

ε-動作を含まない非決定性有限オートマトンに変換

ε1 = 1 ε = 1

ε-動作を含む非決定性有限オートマトンを

ε-動作を含まない非決定性有限オートマトンに変換

p

p

p

ε1 = 1 ε = 1

ちょっと練習

… … … 等は受理される

ε1 ^{= 1} ε = 1

_p

^p

ε1 ^{= 1} ε = 1