2014-07-10

日記

 よくわからないが早く目が覚めた。風の音で。起きて洗濯回して喫茶店行って過去問解いて、アルバイト先経由して大学行って講義受けて図書館でちょっと勉強してスクリプト遊びして帰ってきた。アニメ見たりポテチ食べたりしてた。おもに形式言語進めてた。

雑記 [IS]

正則言語のPumping Lemma
・L⊆Σ*を正則言語とする。このとき、ある定数N>=1が存在して、Lに属する長さがN以上の任意の記号列xに対して、xの分解x=uvwで次の条件を満たすものがある。
 1. 1<=|v|<N (繰り返しの要素がある)
 2. 任意の非負整数mに対してuv^(m)w∈L (その繰り返しの要素を0回以上重ねたものも言語Lに属している)
・証明:N=|Q|(状態数)とする。|x|>=NとなるLの記号列xについて、xはMによって受理されるので、xのMによる受理計算が存在する。Mの状態数はNであり、xの長さn>=Nであるので、受理計算p0~pnには同じ状態が少なくとも2つ現れている。この状態をpi=pj(i<j)として、x=a1...anをu=a1...ai,v=ai+1...aj,w=aj+1...anとする(このvの定義により、ある状態piに遷移するai/それと同じ状態pjから遷移するajという2つの記号を指定し、その間の記号列vを切ったり増やしたりことができる)。1<=|v|<Nである。また、任意のm>=0に対してpi=pjだからi~jのm回の繰り返しは受理される(厳密には受理計算の流れを書いたほうがいい)。
(証明の要点は、状態数Nに対してそれより長い記号列を投げたら状態の繰り返しが起きるはずなので、その状態の始点と終点に対応する記号を切って繰り返し対象にすればOKという点。これが正則でない言語でアウトなのは、繰り返しが作れないから:だいたい繰り返しを0回や無限回にした記号列が言語から外れてしまう。正則でないことは背理法でこれを使って証明する)
 &gt;と&lt;わざわざ書かなきゃいけないのかよ、と少し思った。面倒だった。

広告を非表示にする