第１１回：251 252pdf 最近の更新履歴 Hideo Fujiwara

{ } ➡

{ …} =　 { } {ε …} = { } { } ➡

{ …} = {ε …} { } = { } { } ➡

{ …} = { } {ε …} ➡ ?

復習： 正規集合から正規表現へ

{ } ➡

{ …} =　 { } {ε …} = { } { } ➡

{ …} = {ε …} { } = { } { } ➡

{ …} = { } {ε …} = { } { } ➡

復習： 正規集合から正規表現へ

{ …} = { } {ε …} = { } { } ➡

{ε …} = { } ➡

{ …} = { } _U { …} ➡ ?

{ …} = { } {ε …} ➡ ?

復習： 正規集合から正規表現へ

{ …} = { } {ε …} = { } { } ➡

{ε …} = { } ➡

{ …} = { } _U { …} ➡

{ …} = { } {ε …} ➡

復習： 正規集合から正規表現へ

➡ { }

復習： 正規表現から正規集合へ

➡ { }

復習： 正規表現から正規集合へ

➡ { }

復習： 正規表現から正規集合へ

➡ { … }

復習： 正規表現から正規集合へ

➡ { }

復習： 正規表現から正規集合へ

➡ { … }

復習： 正規表現から正規集合へ

復習： 

{ 0

1 ¦ i 0 } = 0*1

{ 01

¦ i 0 }  = 01*

0 1

復習： 

{ 0

1 ¦ i 0 } = 0*1

{ 01

¦ i 0 }  = 01*

0 1

{ 0

1

¦ i 0 }  は正規表現できない

０の個数を数えなくて良い

復習： 

{ 0

1 ¦ i 0 } = 0*1

{ 01

¦ i 0 }  = 01*

0 1

{ 0

1

¦ i 0 }  は正規表現できない

０の個数を数えなくて良い

０と１の個数 i が同じかを判定し

ないといけないので、i を数える必

要がある

６２∼６５ページ

教科書の説明は、そのままでは難しいので、

ここでは、例を使って、説明していきます。

正規表現は？

正規表現は？ 1

1

１^＊

  正規表現は？

1

0 ^{正規表現は？}

1

0

^(0+1)*

正規表現は？

正規表現は？

正規表現は？

６２ページ

６２ページ

６２ページ

別の例（最終状態が二つある例）

別の例（最終状態が二つある例）