読者です 読者をやめる 読者になる 読者になる

ネギ式

適当に生きるおっさんのブログ

オートマトンについて二つ

直接なにかの書籍に関係するということもないけれど、先日オートマトンについて考えたので、忘れないうちに関連することを二つ書いておこう。

本当の有限ってやつを見せてやりますよ

無限については多くの人が語っているが、有限について語る人はそれに比べれば多くない。希少価値を狙おう。

有限オートマトンの有限は、まさに本当の有限、誰もがこれは有限だと認める有限である。そのポイントは後出し禁止である。じゃんけんと同じだ。以上。

逆に、後出しという対応は強力なので、結果的に有限の数であっても、純粋な本物の有限とは扱われない(ことが多いある)のだ。二人の子供がより大きな数(自然数)を言うというゲームをしたとすれば、後から言ったほうが大きな数になる。これは自然数が無限個あるということに対応しているので、なかなかに不純なのである。

しかし、最近のプログラミング言語は動的割当が得意なので、うっかりすると後出しで配列サイズを決めたり出来るから困りものである。COBOLとかを使おう。

非決定性はゲームの木の探索

非決定性って言われると、オートマトンを現実のプログラムとして作る時にランダムに状態遷移を選ぶのかって思って混乱するけれど、そうではない。可能な状態遷移をすべて試せばいいのだ。可能なものをすべて試すなんていうのは、プログラミングの基本であり、どこにも悩む要素はない。ただし、バカ正直に全部試す必要はなくて、受理状態が見つかればそこで止める。全部探して、受理状態が見つからなければ、入力は受理されない。

これで私がこだわっている、「文法的に正しくない文に対しては正しくないと出力する」ということも問題なく実現できる。

ただし、入力なしで状態遷移するε動作というやつがあると少し厄介だ。探索がループする可能性がある。オーソドックスなオートマトンの本で非決定性の後にε動作が導入されるのも納得できるだろう。それに対する対応としては、オートマトンの定義を同値なものに変えて探索がループしないようするか、または、探索がループしていることを検出するようなプログラムにする必要があるだろう。

 

無限と有限のあいだ (PHPサイエンス・ワールド新書)

無限と有限のあいだ (PHPサイエンス・ワールド新書)

 

 

川添愛「白と黒のとびら」と他のオートマトン本の話の流れとポイントの比較

川添愛の「白と黒のとびら」についての批判を書こうとしているが、いろいろ面倒である。まずプッシュダウンオートマトンと文脈自由文法までの話の展開を比較してみたいと思う。

オートマトン・言語理論の基礎 米田政明監修

以下、この本を米田本として参照する。米田本はこの三冊の中では(情報系の人にとっては)オーソドックスなスタイルである。

  1. 有限オートマトン
  2. 非決定性有限オートマトン
  3. ε動作非決定性有限オートマトン
  4. 最簡形の決定性有限オートマトン
  5. (ε動作)決定性プッシュダウンオートマトン
  6. 非決定性プッシュダウンオートマトン
  7. 形式文法
  8. 正規文法と有限オートマトン
  9. 文脈自由文法とプッシュダウンオートマトン
  10. オートマトンと形式文法の関係
  11. 言語の階層構造(繰り返し定理が出て来る)

これで終わりじゃなくてチューリンングマシンの話もあるけど、とりあえず関係ありそうなところだけ並べた。他の本も同様。初めにオートマトンについてまとめて述べて、後から形式文法について述べ、形式文法とオートマトンの関係を述べるという流れである。また、決定性オートマトンについて述べてから、非決定性オートマトンについて述べている。

決定性プッシュダウンオートマトンのε動作については以下の注意書きがある。

すべてのq(∈Q)、Y(∈Γ)について、もしδ(q, ε, Y)が定義されているならば、すべてのa(∈Σ)に対してδ(q, a, Y)は定義されない。--- p64

 いやここだけ引用しても記号の定義がないから意味が通じないけれど、ε動作には強い制約があるということである(あるスタックトップ記号に対してε動作があるなら、そのスタックトップ記号と他の入力記号の組み合わせでの遷移はないという意味らしい。これにより決定性が保証される)。

オートマトンは形式文法とは完全に独立に定義されている。学問的に面白い(と私が勝手に思う)ところは、

オートマトン・言語理論 富田悦次/横森貴共著

  1. 有限オートマトン
  2. 非決定性有限オートマトン
  3. 正規表現
  4. 形式文法
  5. 文脈自由文法(反復定理を含む)
  6. 単純決定性プッシュダウンオートマトン
  7. 決定性プッシュダウンオートマトン
  8. 非決定性プッシュダウンオートマトン
  9. 非決定性プッシュダウンオートマトンと文脈自由文法の相互変換

有限オートマトンの次に形式文法が来て、その後プッシュダウンオートマトンになるという構成である。しかし、米田本にない、単純プッシュダウンオートマトンという項目がある。これはプッシュダウンスタック以外の状態を持たないという形式のオートマトンであり、単純化されている分だけわかりやすい。

そのはずなのだが、状態が一つしかないので、ここでこの文字が来たらそれ以後はどんな文字が来ても受理しないという不受理状態への遷移が出来ない。受理状態というのもないので、入力文字列が終わった時にスタックが空なら受理という定義になる。しかし、入力文字列が終わる前にスタックが空になると困ったことになる。

スタックだけを使ってそういう問題にうまく対応することはできるのだが、この本ではその辺の説明が大幅に不足しているように思う。

決定性プッシュダウンオートマトンのε動作の制限については、米田本と同様に説明があった。それ以上の説明として、ε動作はは事実上その後スタックが空になる時にのみ使われるという説明もあり親切である。

私が個人的に重視する以下の点にはちゃんと触れている。

白と黒のとびら 川添愛

  1. 有限オートマトンと簡約化
  2. 形式言語から有限オートマトンの構成
  3. 自動販売機としての有限オートマトン(アルファベット三文字)
  4. ε動作非決定性プッシュダウンオートマトン
  5. 反復補題(繰り返し定理)
  6. 文脈自由文法とプッシュダウンオートマトンの等価性

アルファベット三文字のオートマトンが出てくるのはよい。白と黒は説明が簡単になるように使われているだけで、コンピュータの中では2進数……とかいう話とは一切関係ないことだから。

軽く言及されているだけの部分を除くと、非決定性を扱うのが「4.ε動作非決定性プッシュダウンオートマトン?」なんだよね。いきなり難しいのが出てきたぞ。その結果、私が個人的に重視している

この二つは登場しない。そして

  • 独立に定義された形式文法の生成する言語と、オートマトンの受理する言語が等しくなる。

この部分なのだが、「4.ε動作非決定性プッシュダウンオートマトン?」とクエスチョンマークを付けているように、これは情報系のオートマトンの本で最初に導入されるプッシュダウンオートマトンと比較するとかなり変わっている。実は、米田本の「非決定性プッシュダウンオートマトンと文脈自由文法の相互変換」の部分で、文脈自由文法から構成されるプッシュダウンオートマトンがこの「4.ε動作非決定性プッシュダウンオートマトン?」にそっくりなのだ。つまり、文脈自由文法と独立に定義されたものではなく、文脈自由文法から構成されたものを最初に持ってきているわけだ。これで、後に等価性を示したと言われても、私としては納得できない。

非決定性プッシュダウンオートマトンは難しい

確かに、非決定性というのは難しい。機械というものはいつでも同じ動作をするものという考えがある。その上、決定性有限オートマトンの定義のところで、同じ状態、同じ入力に対していつでも同じ状態遷移をするって定義したわけだし。

それだけでなく、非決定性がある場合、私が重視している「正しくない文法の入力に対しては正しくないと答える」ということが難しくなる。

一方、生成規則にあってオートマトンの非決定性に相当する「同じ非終端記号から二種類以上の生成規則がある」というのは理解しやすいようだ。自然言語でもそういうところがあるから。あるいは、文を作る時には自由に作れるという考えがあるからだろうか。

そこで、非決定性より先に文の生成規則をやって、それに対応させる形で非決定性を導入すればわかりやすいと考えたのかもしれない。いやあ、でも独立性が損なわれてしまうと、その後の等価性の証明が全然証明にならないという重大な問題が発生してしまう。

その上、プッシュダウンオートマトンというものがやたら難しく見えてしまうという問題もある。

 

オートマトン・言語理論の基礎

オートマトン・言語理論の基礎

 

 まだ、書くかもしれないし、もう書かないかもしれない。

 

2017春アニメ1話感想その6

ほんとまとめて書いてあったほうが読む方は楽ってのは、わかってるんだけど、見てしばらくすると忘れてしまうんだよ。2話まとめているのが、せいいっぱいなのだ。勘弁な。

ゼロから始める魔法の書

なんか今期アニメは全般的に分かりやすいような気がするのだが、これもまたわかりやすい話のような。破綻がないというか大人しいというか。まあ、破綻しているのがいいという訳ではないのだけれど。やはり物足りないような気もする。

あと、なんか魔法の説明をするのがこれ以外にもあったな。アレだ、ダメな教師の話。どちらの作品についても、そこは期待していないから大丈夫だ。切るような問題点もないけど、見続けたいような強い魅力もない気がする。

 

 

ソード・オラトリア

例の紐の外伝。あれっ、例の紐ってこんなにシリアスな話だったっけ? 視聴者がネタ扱いしただけで、実は最初から大真面目だったのかも。これ、もとから異世界なのかゲーム世界なのかどっちつかずという傾向があったのだが、シリアスでやられると益々そう感じる気がする。

まあ、今の若い人にはゲーム世界でない異世界など想像できないのかも知れないが。外伝をアニメ化したのは、本編のストックが足りないからだろうか。そうでなければ、本編の続編をアニメにした方がよかったと思う。

シリアスやるなら、灰と幻想のグリムガルやって欲しいんだけど。おっさんのオレはマイナーだから希望はなかなか通らない。

 

 

2017春アニメ1話感想その5

ほんとだらだらと書いてるなぁ。まあ、ブログってそんなものだろう。

覆面系ノイズ

そもそも音楽そんなに聞かないので、ノイズっていうのがどういうのかよくわからんのだが、このアニメはいいと思う。主人公が情熱的というか変なんだけど、そこがいい。男二人も妙に天才的だけど、まあそれもいい。

残念なのは、観客モブの動き。ああ、演奏シーンが作画的に苦しいのは分かるけど、この観客モブは、そこで観客の反応を入れるという演出といい、またその観客の動きといい、実に残念な出来になっている。バンドメンバーの止め絵の方がよかったんじゃないかなぁ。

なんか俺の見た評判はそんなによくなかったんだけど、ノイズという音楽のせいかな?

 

 

sin 七つの大罪

前にやった少年漫画のアニメ化のやつの続きかと思ったら、違う作品だった。

エロアニメですな。しかし、エロすぎて規制マークと光がバンバン入って、普通のアニメよりずっと見えない。パンツも見えない。はいてないのか? これは、もう円盤を売るための宣伝という作りなんだろう。いやあ、勘違いしたままでいてもよかった。あ、コミックスを売るためのものか。

 

sin 七つの大罪 1 (ホビージャパンコミックス)

sin 七つの大罪 1 (ホビージャパンコミックス)

 

 

書籍批判:オートマトン・言語理論第二版 富田悦次/横森貴 共著

まず、川添愛による「白と黒のとびら」の批判をしようと思ったのだが、そのためにオートマトンの本としてこの本を調べた結果、先にこの本の批判をしようと思った次第である。

だが、それが面倒くさい。すでに書く前から気力喪失している。こんなん書いても誰も読まないし、せいぜい反応するのは著者の援護する人くらいだろうし、誰のためにもならんじゃないの。だるい。

しかし、俺も手斧を持ったはてな。逆襲が予想されようとも手斧を振るうのだ。

 

形式言語オートマトン生成文法

形式言語というのがあって、これは言語の意味は問わずに、文法だけを問題にする。ある言語の文法に一致するかどうかだけを問題にするのである。その場合に文法を判定する方法が二つある。

ひとつは、文法に合っている文も合っていない文もどちらも受け付けて、その上で、この文は文法に合っている、この文は文法に合っていないという判定を下すという方法である。この判定を行う機械がオートマトンである。

もうひとつは文の生成規則を定めて、その生成規則から生成される文はすべて文法に合っているし、生成される文でなければ文法に合っていないとする方法である。文法に合った文は一般には無限に存在するので、文を全部生成してみせることは出来ない。

自然言語でも似たようなことはあって、日本人が聞いて日本語だと思うものが日本語であるという判定と、日本人が話す言葉が日本語であるという判定に対応すると考えてもよいだろう。

オートマトンとプログラム

一方、オートマトンというのは自動人形というその語源からしても、機械やコンピュータプログラムのモデル化であるとも考えられる。自動販売機のモデルとも言える。オートマトンに対しては同じ動作を行うコンピュータプログラムが作成できる。(あー、非決定性を考えるとちょっと嘘だな)

オートマトン・言語理論 第二版

オートマトン・言語理論 [第2版]

オートマトン・言語理論 [第2版]

 

で、そういうオートマトン形式言語の理論というのは情報科学では、基礎的な理論ということで、学生向けのやさしい教科書が何種類も出版されている。ワシが独学で情報系の勉強をした時には、「岩波講座情報科学6:オートマトン形式言語理論と計算論」という本を読んだものだが、なかなか難しくて理解できなかったものじゃ。しかし今は情報科の学生向けの本でもやさしい本がたくさんあってうらやましい。

やさしい、わかりやすい本

しかしながら、コンピュータについて多少なりとも知っている人なら、気が付くかもしれないが、やさしい、わかりやすいことを目的とした本がわかりやすいとは限らない。

そもそも「わかる」とはどういうことかという定義をしなければ正確な議論は出来ないのだが、その定義自体が紛糾するので、議論が始まらないという問題がある。しかし、「プログラマーがあるオートマトンの概念をわかる」という点については「そのオートマトンを表すプログラムを作れる」というように定義してもよいのではないか。わかったつもりになっていても実際にはわかっていないことは多いのである。わかってるならプログラムを作れってことだ。それがプログラマーである。オートマトンの理論には難しいオブジェクト指向関数型プログラミング圏論も知る必要はない。

プッシュダウンオートマトン

さて、私が上記の本で問題にしているのはプッシュダウンオートマトンの記述である。だいたいオートマトンの本では、有限オートマトンはやさしく、プッシュダウンオートマトンから難しくなり、チューリングマシンは難しいっていう感じなのだが、そのへんはやさしい本でも変わることはない。やさしい本の記述の主体はプッシュダウンオートマトンになる。というかプッシュダウンオートマトンと文脈自由文法の関係が本のクライマックスと言えるだろう。

そしてプッシュダウンオートマトンの主役であるスタックプログラマーならよく知っているデータ構造である。そしてプログラマーでない人でも知っておいて損のない、比較的簡単で重要な概念である。説明はwikipedea:スタックでも見て欲しい。

実は「白と黒のとびら」でもそんな風なところが気になって確認のために、上記の「オートマトン・言語理論第二版」を読んだ次第なのである。

オートマトン・言語理論第二版 例4.9

f:id:ad2217:20170415100021p:plain

上の画像は、「オートマトン・言語理論第二版」の120ページの例4.9からの引用である。このプッシュダウンオートマトンプログラマーの人は理解してプログラムを作ることが出来るだろうか? 記号の意味などを調べるためには是非上のリンクから本を購入して読んで欲しい。その上で、この例のオートマトンのプログラムを作れれば、わかった理解したということになるだろうし、作れなければわかりにくい、理解しにくいということになるだろう。

さらに理解を助けるためにスタックがどう変化するかという図もある。

f:id:ad2217:20170415100548p:plain

上の画像は、「オートマトン・言語理論第二版」の121ページの図4.9からの引用である。図まであって分かりやすいから簡単にプログラムが作れるであろう。

では、プログラムのテストのためのテストケースを挙げておこう。

  • 入力 → 出力
  • ab → 正しい(文法どおり)
  • aabb → 正しい(文法どおり)
  • baabb → 正しくない(文法違反)
  • abb → 正しくない(文法違反)
  • aaba → 正しくない(文法違反)

このテストケースを満たすプログラムが作れたかな? 俺には作れなかったよ。 どうしてこうなった?

 オートマトン・言語理論の基礎

わからない時には、更に別の本を参照するのである。それが文献探索の底なし沼というもの。

オートマトン・言語理論の基礎

オートマトン・言語理論の基礎

 

 この本にも当然ながらプッシュダウンオートマトンについての記述がある。そして、上の例題をプログラムする上で決定的に重要な情報が書かれていた。

 動作を停止したときの状態qnが受理状態の1つ(Fの要素)で、pd-スタックが空である(αnが空で、ボトムマーカーZ0のみである)なら、Mは入力ωを受理する。反対に、状態qnが受理状態の1つでない、あるいは、pd-スタックが空でないなら、Mは入力ωを拒否する。すべての入力を読み終わる前に、動作関数が定義されていなくて動作を停止することもあるが、その場合にも入力ωを拒否すると考える。

 「オートマトン・言語理論の基礎」67ページより。数学記号がうまく表現できていないが、記号の意味などは、上記リンクからこの本を購入して確認して欲しい。

この情報があればプログラムを作ることができるが、分かりやすくはない。俺ならこういう記述があったら、動作が定義されていないところでは例外を投げる。しかし例外を投げっぱなしでは先のテストケースに落ちるので、例外をキャッチしてテストケースに合うような値を返すようにするだろう。

しかし、それでは正しいとは言えないだろう。それはプッシュダウンオートマトンの定義に合っているかどうか分からないのである。プッシュダウンオートマトンは極めて限定的な機械なので好き勝手にプログラムしてはいけないのだ。

私なりの解決

例4.9でちゃんと動作を定義するのが、正しい、そしてわかりやすい解決であろう。

数学記号を表示できないので簡略な書き方にする。スタックトップがSで、入力がbの時スタックトップのSをXにするという場合に(S, b) → X と書くことにすると追加する規則はこうなる。

  • (S, b)→ X
  • (B, a)→ X
  • (X, a)→ X
  • (X, b)→ X

 しかし、なんということでしょう。これではまだテストケースを通らないのだ。実に難しい、わかりにくい例である。abbという入力をどうするか? これは米田氏の本ならスタックボトムに記号があるので解決可能なのだが、富田・横森両氏の本ではうまくいかないのである。(スタックが空の場合はスタックトップを参照できないのである)*1

そもそも富田・横森両氏の本では、状態遷移規則にない入力が来た場合の動作についての何も書かれていないので、もともとどうにもならないのである。(こんなことを書いていて、実は本のどこかに書いてあったら私の大恥である。そして、私の人生にはそれに匹敵するような大恥は何度もあるのだ)

結論

プログラムが作れないということは、本の説明がわかりにくいということだ。……と思うのだが、どうだろうか。

結論その2:ユニットテスト、テストケースという考え方は強い

但し書き

このブログに書かれていることは、著者の個人的見解であり、著者の所属する組織の公式見解ではない。

 

*1:スタックが空かどうかプログラムで判定することは出来るので、毎回スタックが空であるかどうか判定を入れるということは可能である。ただし、状態遷移規則はスタックトップを参照する形でしか書けないのが問題である。

2017春アニメ1話感想その4

だらだらと1話の感想を書いている訳ですが、それはdアニメストアがだらだらと配信を開始するからである。こんな何周遅れか分からないようなアニメ感想書いても集客できないよ。

でも1話切りでも記録しておくということには意味があると思うので記録として残すのです。ログだからね。つまりは航海日誌だからね。

終末なにしてますか? 忙しいですか? 救ってもらっていいですか?

長いタイトルだ。タイトルから想像していたのよりはずっと大人しい普通の異世界アニメだった。まあタイトルからすると異世界ではなくて遠未来かも知れないけど。終末感がないので、異世界だと感じるんだな。

獣耳がないのでフードや帽子で隠すってところがあったけど、アニメでは獣耳たちはフードも帽子もかぶっていないので、バレバレだと思う。帽子屋という商売が成り立つのか不思議である。アニメ「ワールド・デストラクション」では獣耳を付けていたわけで、そのくらいの対応はするよなぁと思った。

しかし、比較しちゃ悪いけど「人類は衰退しました」は終末感もあるし、傑作だったことよのう。

まあ、「人類は衰退しました」と比較すると劣るけれど、悪くはない。

 ひなこのーと

タイトルから想像していたのとは違って、面白そうな1話であった。演劇をするアニメらしい。なかなか珍しいかも。演劇風のアニメというのもあるが、これはそうではなくて日常系っぽいほのぼのしたものだ。

まあ、演劇も真面目にやると厳しい世界らしいけど、ゆるい感じで進むのだろうか、それとも厳しいところも出てくるのであろうか? 期待と不安から視聴せずにはいられない。

 

 エンディングのアニメもいい。

TVアニメ「 ひなこのーと 」エンディングテーマ「 かーてんこーる!!!!! 」

TVアニメ「 ひなこのーと 」エンディングテーマ「 かーてんこーる!!!!! 」

 

 

スーパーで買物中に火事に会ったらどうするか?

スーパーで買物中に火事に会ったらどうするか?

というようなことをちょっと考えてみた。

まず、問題なのは買い物カゴをどうするかである。持ったまま逃げる訳にはいかない。それでは万引きになってしまう。しかし、棚に商品を戻す余裕はないだろう。

こういう場合、店内放送や店員の誘導に従うのが正しい行動だと思うが、放送でただ「落ち着いて避難して下さい」というだけで、買い物カゴをどうするか、案内がなかったらどうしたらいいのだろうか。店側もそこまで想定していないかも知れない。何も言わなかったとしても、持ったまま逃げて万引き扱いされたのではたまらない。

そうすると、その場に買い物カゴを置き去りにして避難するということになるだろう。冷蔵・冷凍食品とかカゴに入っていると、なんとなく気が引ける気もするが、燃えてしまえばどのみち失われるのである。

問題は火災が誤報だった場合だが、店から避難指示があった以上は、買い物カゴ置き去りによる損害は店がかぶることになるのは、店としても仕方がないだろう。

他の客が買い物カゴを持ってためらっているうちに、落ち着きつつ他人を出し抜いて先に避難するのがよかろう。

出入り口は広く開けて

なお、店に入ろうとしたところで警報を聞いて入ろうかどうしようか悩んだり、一旦店から出たものの誤報だったら戻って買い物をしたいなどの理由で、出入口付近でだらだらとたむろしている人がいるかも知れない、それこそ大問題である。誤報だと思っても出入り口は広く開けておけよ。おまえらのせいで人が死ぬぞ!