有限オートマトンをこのように図示したとき、頂点r0からr1,r2,…を経てrnへ至る‘道’は δ(ri-1,ai)＝ri　（i＝1,2,…,n） というnステップの状態遷移を表す。両端のみに注目すれば δ(δ(…δ(δ( […]

「有限オートマトン」は記号列を読んで識別する自動機械の数学的モデル（記憶容量が有限）。 入力前に特定の初期状態にセット 記号列を入力すると先頭から1文字ずつ読む 読んだ記号によって「状態」が変わり、全部読み終えたときの状 […]

定理1.16 X⊆Σ＊が正則集合ならばXの商　x\X　（x∈Σ＊）のうち相異なるものは有限個である。 　証明略。 定理1.18 X∈Σ＊が正則集合ならば、任意の語zによるXの商z\Xは正則集合である。 　証明略。 　除算 […]

正則集合の構成に関する帰納法 φについて成り立つ 各{a}　（a∈Σ）について成り立つ 正則集合X,Yについて成り立つと仮定しとき、X∪Y,XY,X＊についても成り立つ 任意の集合X⊆Σ＊および語y∈Σ＊に対して y\X […]

定義：Σ上の正則集合 空集合φは正則集合 a∈Σ　⇒　{a}は正則集合 X,Y⊆Σ＊が正則集合　⇒　X∪Y,XY,X＊は正則集合 　いかにも帰納法が使えそうな感じの定義である。あれ？　ε∈Σ＊だけど、文字としてΣに含まれ […]

　1-2.可換な語…は飛ばす。初学者は飛ばしてよいと前書きにあった。 語に対する連接をもとに言語に対する連接演算を XY＝{xy｜x∈X,y∈Y}　（X,Y⊆Σ＊） によって定義する。とくに空集合φおよび空語のみからなる […]

定義：Σ上の語x,yに対して、∃z∈Σ＊｜y＝xz　であるとき、xはyの接頭語であるといい、x≦yで表す。 　本書では「≦」ではなく、「＜」の下の斜線だけが2重になった記号を使っているが、自然数の大小関係「≦」でもその記 […]

問1.1　h:Σ＊→Γ＊　が準同型写像のとき h(xy)＝h(x)h(y)　（x,y∈Σ＊） であることをyの長さに関する帰納法で証明せよ。

定義：Σ＊の部分集合を「言語」という。 　それはさておき。 Σ＝{a}のとき、Σ＊＝{a}＊と自然数の集合Nは1対1に対応付けられる。 　{a}＊とは、{ε,a,aa,aaa,…}のことだ。N＝{0,1,2,3,…}と対 […]

定義：Σ上の語x＝a1a2…an,y＝b1b2…bmを続けてできる語a1a2…anb1b2…bmをxとyの連接（concatenation）、または積とよび、xyと書く。 　そういえば、Excelにおいて文字列を連結する […]