５９∼６０ページ
５９∼６０ページ
５９∼６０ページ
φ は正規集合 {ε} は正規集合
Σ = {0,1} とすると {0}, {1} は正規集合
{0}*, {1}* は正規集合
５９∼６０ページ
φ は正規集合 {ε} は正規集合
Σ = {0,1} とすると {0}, {1} は正規集合
{0}*, {1}* は正規集合 {0}{1}*
{0}{1}* {11}
{0}({0}{1}* {11})* は正規集合
６０ページ
６０ページと７４ページ
この言語を受理する有限オートマトンを作れる
６０ページと７４ページ
この言語を受理する有限オートマトンを作れる
この言語を受理する有限オートマトンは作れない
０の個数と１の個数が同じであることを知るには、最初に入ってくる ０の個数を記憶しないといけない。しかし、有限オートマトンの状態数 は有限個数なので、それより多い０を記憶することはできない。
６０∼６１ページ
６０∼６１ページ
φ は正規表現 ε は正規表現
Σ = {0,1} とすると 0, 1 は正規表現
0*, 1* は正規表現
６０∼６１ページ
φ は正規表現 ε は正規表現
Σ = {0,1} とすると 0, 1 は正規表現
0*, 1* は正規表現 01*
01*＋11
0(01*+11)* は正規表現
６１ページ
６１ページ
正規集合 正規表現
{0, 1} = {0} U {1} 0+1
{0, 1}* = { {0} U {1} }* (0+1)*
{0}* = {ε, 0, 00, 000, … } 0*
{1}* = {ε, 1, 11, 111, … } 1*
{0}*{1}* 0*1*
= {ε, 0, 00, 000, … }・{ε, 1, 11, 111, … } = {ε, 0, 1, 00, 01,11, 000, 001, 011, 111, … }
{ {0}*{1}* }* (0*1*)*
= {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, … }
= {0, 1}* = (0+1)*
正規集合 {0, 1}* の 正規表現は (0 + 1)* と (0*1*)*
６１ページ
で等価である
６１ページ
{ } ➡
例題 正規集合から正規表現へ
{ } ➡
{ …} ➡
例題 正規集合から正規表現へ
{ } ➡
{ …} ➡
{ …} = {ε …} { } ➡
例題 正規集合から正規表現へ
{ } ➡
{ …} ➡
{ …} = {ε …} { } ➡
{ …} = { } U { …} ➡
例題 正規集合から正規表現へ
{ } ➡
{ …} ➡
{ …} = {ε …} { } ➡
{ …} = { } U { …} ➡
{ …} = { } {ε …}
➡
例題 正規集合から正規表現へ
➡ { }
例題 正規表現から正規集合へ
➡ { }
➡ { …}
例題 正規表現から正規集合へ
➡ { }
➡ { …}
➡ { …}
例題 正規表現から正規集合へ
➡ { }
➡ { …}
➡ { …}
➡ { } U { …}
= { …}
例題 正規表現から正規集合へ
➡ { }
➡ { …}
➡ { …}
➡ { } U { …}
= { …}
➡ { } {ε …}
= { …}
例題 正規表現から正規集合へ
➡ { }
➡ { …}
➡ { …}
➡ { } U { …}
= { …}
➡ { } {ε …}
= { …}
➡ { } { } {ε …}
= { } {ε …}
= { …}
