既述のLijkのjに関する帰納法によりLijkが正則集合であることが示される。 定理2.3 有限オートマトンの受理集合は正則集合である。 　省略しすぎ？ 　ま、まあ、それよりも「正則でない集合」がどんなものか、前から気 […]

問：スターツールで端正な星形を描くための第1半径・第2半径の比を求めよ。 解答： Adobe Illustratorのスターツールでいう第1半径・第2半径とは、内側の多角形に外接する円の半径r1と外側の多角形に外接する円 […]

この節では、初めに前節の定理の逆、すなわち有限オートマトンの受理集合が正則集合であることを示し、次いで有限オートマトンの拡張である日決定性有限オートマトンと有限遷移図について述べる。 有限オートマトン　M＝(Q,Σ,δ, […]

例2.2 正則集合X＝(ab＊a)＊を受理する有限オートマトンM＝(Q,Σ,δ,q0,F)を構成しよう。 　いや、いきなりソレはついていけないので、もっと単純なものにしよう。 　Σ＝{日本語のひらがな}、正則集合X={「 […]

この節では任意の正則集合に対してそれを受理する有限オートマトンが存在することを示す。 　任意の正則集合、とは、語の集合で変態的でないもの、程度に考えておこう。つまり、たいていの語の集合について、ある語がその集合に属するか […]

　解答3 　Σ＊aaaΣ＊の部分はこんな感じ（主要部のみ）になるはずだ。 　aをbに変えて同じ形のものを作れば、Σ＊bbbΣ＊の流れができる。初期状態と受理状態を同じところに合わせるとこんな感じ。 　ここで、aaaやbb […]

問2.2　次の各言語を受理する有限オートマトンを構成せよ。 {aa,bb}＊ {aa}＊{bb}＊ Σ＊aaaΣ＊∪Σ＊bbbΣ＊ 　解答 　1. 　言語の仕様（定義）を確認しておこう。　{aa,bb}＊＝{ε,aa,b […]

有限オートマトンをこのように図示したとき、頂点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は正則集合である。 　証明略。 　除算 […]