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

Posted in 自習 on 7月 10th, 2011 by admin — Be the first to comment!

 そういうわけで、

定理2.3
有限オートマトンの受理集合は正則集合である。

が証明された。
 この定理を「集合に関する連立方程式」の考え方で証明する方法が載っている。

有限オートマトンM=(Q,Σ,δ,q0,F)に対して、Q={1,2,…,n}、
Li={x∈Σ|δ(i,x)∈F} (i=1,2,…,n)
とおく。i=q0のときLi=L(M)である。

 今度はLijkは考えない。

このL1,L2,…,Lnについて、次の(1)~(4)が成り立つ。

  • (1)
    Li=∪(j=1 to n)Aij・Lj ∪ Bi (i=1,2,…,n)
    ただし、Aij={a∈Σ|δ(i,a)=j}、Bi={ε|i∈F}

     なお、∪の上下に変数の範囲を書くことが困難なので、下付き文字として(j=1 to n)と記した。

  • (2)
    もし X1,X2,…,Xn⊆Σが、上記のAij,Biに対して
     Xi=∪(j=1 to n)Aij・Xj ∪ Bi (i=1,2,…,n) …※
    を満たすならば、Li⊆Xi (i=1,2,…,n) である。
    つまりL1,L2,…,Lnは上のn個の連立方程式※の最小解である。

     連立方程式を満たす集合Xiがあるとすると、必ずその中にLiを含んでいる、ということは、その連立方程式を満たす集合のうちではLiが一番小さい、ということだ。

  • (3)
    任意のAij,Biに対して、連立方程式※の最小解X1,X2,…,Xnは以下のように求められる。
    n=1のとき、X1=A11・B1.
    n>1のときは次のように考える。
    連立方程式の第n式を
    Xn=∪(j=1 to n)Anj・Xj ∪ Bn
     =AnnXn ∪ (∪(j=1 to n-1)Anj・Xj ∪ Bn)
    とし、X1,…,Xn-1を単なるパラメータとみなせばn=1の場合と同様に変形できる。すなわち、
     Xn=Ann・(∪(j=1 to n-1)Anj・Xj ∪ Bn).
    これを、第1~n-1式に代入し、X1,…,Xn-1に関する連立方程式
     Xi=∪(j=1 to n-1)A’ij・Xj ∪ B’i (i=1,2,…,n-1)
     ただし、A’ij=Aij∪Ain・Ann・Anj、B’i=Bi∪Ain・Ann・Bn (i,j=
    1,2,…,n-1)
    が得られる。このn-1元連立方程式の最小解を X1,X2,…,Xn-1 とすると、もとのn元連立方程式の最小解は X1,X2,…,Xn-1,Xn である。
     ただし、Xn=Ann・(∪(j=1 to n-1)AnjXj ∪ Bn)

    n-1元連立方程式の最小解がわかっている前提で、 n元連立方程式の最小解もわかると。

  • (4)
    Aij,Biがすべて正則集合なら、(3)で求めた各Xiは正則集合である。

 (3)の手順をきちんと把握したい。字面ではわかるけど…

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

Posted in 自習 on 7月 7th, 2011 by admin — Be the first to comment!

 省略してしまった証明部分を再読。あとあと効いてきそうなので書いておく。

各i,k∈Qに対して
 Aik={a∈Σ|δ(i,a)=k}
とおく。

 つまり、「状態iのときに与えられたら状態kになるような1文字『a』の集合」がAik

そのとき、j=1に対するLijkは、iから途中1(=j)だけを経由してkに至る際の入力語の集合であるから、
 Li1k=Ai1・A11・A1k ∪ Aik ∪ {ε|i=k} (i,k∈Q)
と表せ、これはΣ上の正則集合である。

 ここが帰納法のswitch(j){case 1:…の部分だ。
 Lijkが、直前に定義したAを用いて、
 「iから1に遷移する文字の集合」「1から1に遷移する文字の集合、任意個の積(任意個だからなくてもよい)」「1からkに遷移する文字の集合」の積
  または(つまり和集合)、
 「iから直接kに遷移する文字の集合」
  または、
 「行き先のkが出発点のiと同じときは空語だけからなる集合(遷移する必要がないから)」
 と書けるといっている。
 ここに登場する個々の集合は{a|a∈Σ}(←これは正則集合だ)の和集合として書けるから、それらの和集合であるLijkも正則集合だ。

 case j>1:…はまた今度。 Read more…

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

Posted in 自習 on 6月 29th, 2011 by admin — Be the first to comment!

 既述のLijkのjに関する帰納法によりLijkが正則集合であることが示される。

定理2.3
有限オートマトンの受理集合は正則集合である。

 省略しすぎ?
 ま、まあ、それよりも「正則でない集合」がどんなものか、前から気になっている。
 定義によれば、正則集合の積集合 X∩Y は正則集合と定められていない。しかし、単純に{a,b,c,d}∩{c,d,e,f}={c,d} としたところで、これは正則集合の和集合{c}∪{d}と同じなのでやはり正則集合になってしまう。何か反例はないかな…。

正則集合の無限個の和は必ずしも正則集合ではない。
問1.18(3) X={anbn|n=0,1,2,…}は正則集合でないことを示せ。
正則集合が正則演算のほかに反転、除算、正則代入などに関して閉じたクラスをなすことを見てきたが、その他の演算についてはどうだろうか。

 ヒントはこのあたりだろうか。

Illustratorで星形を描く 解答編

Posted in Illustratorの数学 on 6月 29th, 2011 by admin — 5 Comments

:スターツールで端正な星形を描くための第1半径・第2半径の比を求めよ。

解答
Adobe Illustratorのスターツールでいう第1半径・第2半径とは、内側の多角形に外接する円の半径r1と外側の多角形に外接する円の半径r2のことだろう。
第1半径と第2半径
したがって、下図において線分BDと線分ACの長さの比を求めることに等しい。
五芒星の各線分
五芒星の各線分の比が黄金比であることを利用する。じつは
 BD:BC=BC:AC=1:(1+√5)/2
であるのだった。 →Wikipedia参照
これにより、
 r2=r1×(1+√5)/2×(1+√5)/2
  =r1×(3+√5)/2
  ≒r1×2.618033998…

これが結果である。
 BD:AC=1:(3+√5)/2

検証
スターツールの第1半径に10、第2半径に26.18(桁数は適当に調整される)を指定して作図すると、
スターツールのダイアログ端正な星形

ちゃんと端正な星形が描ける。 Read more…

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

Posted in 自習 on 6月 23rd, 2011 by admin — Be the first to comment!

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

有限オートマトン M=(Q,Σ,δ,q0,F) の状態の集合を {1,2,…,n} とする(状態の名称そのものは本質的でないため、このように仮定しても一般性を失わない)。

 ああ、やっぱり状態の名称はたんなるラベルと考えていいのだな。

このQの各元i,j,kに対して
Lijk
 {a1a2…am
  a1,a2,…,am∈Σ,m≧1,
  δ(i,a1a2…al)≦j (l=1,…,m-1),
  δ(i,a1a2…am)=k}
 ∪
 {ε|i=k}
とおく。

 一目で理解できたらすごいぞ、これ。日本語訳はのちほど。 Read more…

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

Posted in 自習 on 6月 22nd, 2011 by admin — 1 Comment so far

例2.2
正則集合X=(aba)を受理する有限オートマトンM=(Q,Σ,δ,q0,F)を構成しよう。

 いや、いきなりソレはついていけないので、もっと単純なものにしよう。
 Σ={日本語のひらがな}、正則集合X={「あい」}⊆Σとしよう。2文字からなる語1つだけでも正則集合だ。

 定理2.1の証明にしたがって構成する。

 Xの商のなす集合
 Q={x\X|x∈Σ}
  ={あ\X,い\X,…,ん\X,ああ\X,あい\X,…,あああ\X,…}

 であるが、「アタマに何かくっつけたら『あい』になるもの」は、

  • 「『あ』をくっつけて『あい』になる【い】」
  • 「『あい』をくっつけて『あい』になるε」
  • 「εをくっつけて『あい』になる【あい】」

だけだ。だから、
 Q={{「あい」},{「い」},{ε}}
 これは元が3つの有限集合だ。このQを状態の集合と考える。

 状態遷移関数 δ(x\X,a)=xa\X も例示してみよう。
 x\X={「あい」}∈Qの場合、x=εであった。
 a=「あ」とすると、
  δ(x\X,a)=εa\X=あ\X={「い」}.
 a≠「あ」のときは、
  δ(x\X,a)=εa\X=い(etc)\X=φ. ∵「い」などをアタマにくっつけたとき「あい」になるひらがな語は存在しないから。
 x\X={「い」}∈Qの場合、x=「あ」であった。
 a=「い」とすると、
  δ(x\X,a)=あい\X={ε}.
 a≠「い」のとき(たとえば「う」)は、
  δ(x\X,a)=あ・う(etc)\X=φ.
 x\X={ε}∈Qの場合、x=「あい」であった。
 aがなんであれ(たとえば「う」)、
  δ(x\X,a)=あい・う(etc)\X=φ.

 初期状態は ε\X={「あい」} とする。

 受理状態の集合は F={y\X|y∈X}
  ={y\X|y∈{「あい」}}
  ={あい\X}
  ={ε}
 とする。

 図にするとこうなる?

 状態の集合には空集合を含めて、 Q={{「あい」},{「い」},{ε},φ} としなければいけないのかな。 Read more…

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

Posted in 自習 on 6月 22nd, 2011 by admin — 1 Comment so far

この節では任意の正則集合に対してそれを受理する有限オートマトンが存在することを示す。

 任意の正則集合、とは、語の集合で変態的でないもの、程度に考えておこう。つまり、たいていの語の集合について、ある語がその集合に属するか否かを有限の手順で判別できるはずだ、ということかな。

XをΣ上の正則集合、Xの商のなす集合を Q={x\X|x∈Σ} とおく。Qは有限集合である。
このQを状態の集合とする。
状態遷移関数 δ:Q×Σ→Q を次のように定義する。
δ(x\X,a)=(xa)\X ( x∈Σ,a∈Σ)

ややこしいが、Qは集合の集合、高校数学で「族」と習ったものになっている。

状態遷移関数 δ:Q×Σ→Q を δ:Q×Σ→Q に拡張する。
δ(x\X,y)=(xy)\X ( x∈Σ,y∈Σ

 |y|=n,y=a1a2…an とおけば、
 δ(x\X,y)=δ(δ(…δ(δ(x\X,a1),a2)…),an)=a1a2…an\X
 ということだ。

特に x=ε のとき δ(ε\X,y)=y\X である。このことに注意して、Qの元ε\Xを初期状態q0とし、受理状態の集合Fを
F={y\X|y∈X}
とおいて有限オートマトン M=(Q,Σ,δ,q0,F) を構成する。

そうすると、
y∈L(M) ⇔ δ(ε\X,y)∈F ⇔ y\X∈F ⇔ y∈X
∴ L(M)=X.
こうしてXを受理するオートマトンが構成できた。

 ここだけ日本語に直しておこう。
 「ある語yがオートマトンMによって受理される」 とは、
 「『初期状態からはじめてyを1文字ずつ与えていった結果(δ)』が受理状態の一つである」 ということであり、それは、
 「『yをアタマにくっつけたときにXの元になるような語の集合』が受理状態の一つである」 ということと同じで、それはFの定義によれば、
 「yがXの元である」ということと同じなのだ。

定理2.1
任意の正則集合Xに対して、Xを受理する有限オートマトンが存在する。

Read more…

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

Posted in 自習 on 6月 18th, 2011 by admin — Be the first to comment!

 解答3
 ΣaaaΣの部分はこんな感じ(主要部のみ)になるはずだ。

 aをbに変えて同じ形のものを作れば、ΣbbbΣの流れができる。初期状態と受理状態を同じところに合わせるとこんな感じ。

 ここで、aaaやbbbの途中で他の文字が来た場合は、単にエラーにすればいいのかと思ったが、違う。
 たとえば、「***a***aaa***」「***aab***aaa***」「***bbaaa***」などという語もΣaaaΣの元だからだ。
 a…を受け取って左の流れに入った後でも、スタートに戻ったり、右の流れにレーンチェンジすることを考えなければならない。逆も同様。したがって、

 こうなると考えた。
Read more…

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

Posted in 自習 on 6月 14th, 2011 by admin — Be the first to comment!

問2.2 次の各言語を受理する有限オートマトンを構成せよ。

  1. {aa,bb}
  2. {aa}{bb}
  3. ΣaaaΣ∪ΣbbbΣ

 解答
 1.
 言語の仕様(定義)を確認しておこう。 {aa,bb}={ε,aa,bb,aabb,aaaabb,bbaa,…}であって、abとかbabのように同じ文字が2文字連続ではないものは含まないわけだ。したがって2文字目が1文字目と同じだったら受理状態になる。

 丁寧に(かつ題意を汲んで)考えると、アルファベットΣ={a,b} 上のすべての語の集合、
 Σ={ε,aa,bb,ab,ba,aba,…}  の部分集合
 Σ ⊇ {aa,bb}
 …を受理するわけだから、受理しない語(ab,ba,aba,…)も渡される事を考えなければ。

 はて、状態の集合はどう決めればいいんだろう。「受理するかどうか」だけしか情報がないなら、yes/noとか0/1でいいような気もするが。ああ、でも1文字目がaだったときとbだったときで行先は別の状態としなければいけないから、識別のために自然数がいいだろうな。

 Q={0,1,2,3}ということで。これで完成だ。たぶん。

 2.
 同様に考え、Q={0,1,2,3,4}、q0=0∈Q、L={0,3}

3はまた今度。同じように考えればできそうだ。

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

Posted in 自習 on 6月 13th, 2011 by admin — Be the first to comment!

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

これを簡単に
δ(r0,a0…an)=rn
で表す。

δ(q0,x) は有限オートマトンMが初期状態q0から動き始めて、入力語xを読み終わったときの状態。
定義:この状態 δ(q0,x)∈F のとき、Mは語xを受理するという。Mが受理する語の集合をMの受理集合といいL(M)で表す。

 先程の例だと、L(M)={0,1,2}=Q となって、あまり面白くない。