Category Archives: 自習
「思想の中の数学的構造」/山下正男
「思想の中の数学的構造」(ちくま学芸文庫)を読んだ。表紙のデザインも良い。 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