「数学ガールの秘密ノート 丸い三角関数」/結城浩
数学ガールの秘密ノート/丸い三角関数 ◎ いつもながら、こんなむずかしいこと高校時代に思いもしなかったなあ、という感想。
数学ガールの秘密ノート/丸い三角関数 ◎ いつもながら、こんなむずかしいこと高校時代に思いもしなかったなあ、という感想。
「思想の中の数学的構造」(ちくま学芸文庫)を読んだ。表紙のデザインも良い。 p115~ チョムスキーの生成文法あたりは有限オートマトンに与える記号列「語」の定義を思い出した。 p356 複素数の行列表現がwikipedi […]
そういうわけで、 定理2.3 有限オートマトンの受理集合は正則集合である。 が証明された。 この定理を「集合に関する連立方程式」の考え方で証明する方法が載っている。 有限オートマトンM=(Q,Σ,δ,q0,F)に対し […]
省略してしまった証明部分を再読。あとあと効いてきそうなので書いておく。 各i,k∈Qに対して Aik={a∈Σ|δ(i,a)=k} とおく。 つまり、「状態iのときに与えられたら状態kになるような1文字『a』の集合 […]
既述のLijkのjに関する帰納法によりLijkが正則集合であることが示される。 定理2.3 有限オートマトンの受理集合は正則集合である。 省略しすぎ? ま、まあ、それよりも「正則でない集合」がどんなものか、前から気 […]
この節では、初めに前節の定理の逆、すなわち有限オートマトンの受理集合が正則集合であることを示し、次いで有限オートマトンの拡張である日決定性有限オートマトンと有限遷移図について述べる。 有限オートマトン 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 […]