「数学ガールの秘密ノート 丸い三角関数」/結城浩

 数学ガールの秘密ノート/丸い三角関数  ◎  いつもながら、こんなむずかしいこと高校時代に思いもしなかったなあ、という感想。  

「思想の中の数学的構造」/山下正男

「思想の中の数学的構造」(ちくま学芸文庫)を読んだ。表紙のデザインも良い。 p115~ チョムスキーの生成文法あたりは有限オートマトンに与える記号列「語」の定義を思い出した。 p356 複素数の行列表現がwikipedi […]

有限オートマトン2-3.正則集合と有限オートマトン(2) その4

 そういうわけで、 定理2.3 有限オートマトンの受理集合は正則集合である。 が証明された。  この定理を「集合に関する連立方程式」の考え方で証明する方法が載っている。 有限オートマトンM=(Q,Σ,δ,q0,F)に対し […]

有限オートマトン2-3.正則集合と有限オートマトン(2) その3

 省略してしまった証明部分を再読。あとあと効いてきそうなので書いておく。 各i,k∈Qに対して  Aik={a∈Σ|δ(i,a)=k} とおく。  つまり、「状態iのときに与えられたら状態kになるような1文字『a』の集合 […]

有限オートマトン2-3.正則集合と有限オートマトン(2) その2

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

有限オートマトン2-3.正則集合と有限オートマトン(2)

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

有限オートマトン2-2.正則集合と有限オートマトン(1) その2

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

有限オートマトン2-2.正則集合と有限オートマトン(1)

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

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

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

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

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