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

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

Read More..

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

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

Read More..

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

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

Read More..

Illustratorで星形を描く 解答編

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

Read More..

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

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

Read More..

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

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

Read More..

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

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

Read More..

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

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

Read More..

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

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

Read More..

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

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

Read More..