有限オートマトン2-1.定義 その2

有限オートマトンをこのように図示したとき、頂点r0からr1,r2,…を経てrnへ至る‘道’は δ(ri-1,a […]

有限オートマトン2-1.定義

「有限オートマトン」は記号列を読んで識別する自動機械の数学的モデル(記憶容量が有限)。 入力前に特定の初期状態 […]

1-3.正則集合 その4

定理1.16 X⊆Σ*が正則集合ならばXの商 x\X (x∈Σ*)のうち相異なるものは有限個である。  証明略 […]

1-3.正則集合 その3

正則集合の構成に関する帰納法 φについて成り立つ 各{a} (a∈Σ)について成り立つ 正則集合X,Yについて […]

1-3.正則集合 その2

定義:Σ上の正則集合 空集合φは正則集合 a∈Σ ⇒ {a}は正則集合 X,Y⊆Σ*が正則集合 ⇒ X∪Y,X […]

1-3.正則集合

 1-2.可換な語…は飛ばす。初学者は飛ばしてよいと前書きにあった。 語に対する連接をもとに言語に対する連接演 […]

1-1.語 その5

定義:Σ上の語x,yに対して、∃z∈Σ*|y=xz であるとき、xはyの接頭語であるといい、x≦yで表す。   […]

1-1.語 その4

問1.1 h:Σ*→Γ* が準同型写像のとき h(xy)=h(x)h(y) (x,y∈Σ*) であることをyの […]

1-1.語 その3

定義:Σ*の部分集合を「言語」という。  それはさておき。 Σ={a}のとき、Σ*={a}*と自然数の集合Nは […]

1-1.語 その2

定義:Σ上の語x=a1a2…an,y=b1b2…bmを続けてできる語a1a2…anb1b2…bmをxとyの連接 […]