リリカル☆Lisp開発日記

計算量に関して – 矢沢久雄の情報工学“再”入門を祝すCommentsAdd Star経由で、
矢沢久雄の情報工学“再”入門という記事を知ったのですが、
指摘されている通り、確かに内容が激しく怪しいです。
以前、「日経ソフトウエア」という雑誌を読んでいると、
この矢沢さんが書いてある記事があったんですよ。

**
設問 ヘビ
ある世界には、文字だけで出来た不思議なヘビが住んでいます。
このヘビはA種とB種の2種類が確認されていますが、
それ以外の種類がいる可能性もあります。
A種は “>’”の後に1個以上の”=”が並んだ後、”#”が着て、
さらに前と同じ個数の”=”が続き、”~”(半角チルダ)で終わります。
B種は”>^”の後に”Q=”が1個以上並んだ後、”~~”(半角チルダ2個)で終わります。

A種の例:>'===#===~      >'==#==~
B種の例:^Q=Q=Q=Q=~~  >^Q=Q=~~

ヘビを文字列データとして受け取り、
それがどんな種類かを判別して、A種の場合はA、
B種の場合B、A種でもB種でもない場合はNAを出力して
出力するプログラムを作成してください。
(略)
**
(略)
そして、三つ目の方法は、状態遷移図を描いて、
文字列の末尾で終了状態になればパターンが一致したと判定するものです。
これが正攻法かもしれませんが、かなり面倒でしょう。
「オートマトン」という言葉を聞いたことがあるかもしれません。
与えられた入力に対して、内部の状態が遷移(状態を表す変数の値が変化)する
架空のマシンです。
最後の1文字を入力したときに終了状態になることを「入力を受理した」といいます。
つまり判定OKというわけです。
状態遷移図を描く方法はオートマトンの考え方をもとにしています。
(略)
(日経ソフトウエア 2007年 7月号より)

なんだかおかしくないでしょうか。
A種のヘビは = の数をかぞえる必要があるため、鳩の巣原理より、
有限オートマトンで記述できず、状態遷移図も書けないのでは無い気がします。
(プッシュダウンオートマトンなら記述できますが、
それを単に「状態遷移図」と呼んでいいものなのか。)
そう思って編集部に質問のメールを投げてみたんですよ。
そして、返ってきた返事がこれです。

筆者の矢沢久雄さんにも確認したところ，
ご指摘の通りです。
オートマトンは数を数えられないので，
オートマトンを使うことで，ヘビAの「＃」記号の左右にくる
「＝」記号の並び数をバランスさせることはできません。
本文で言及している「状態遷移図」も，もちろん有限オートマトンと
して描くことはできません。
筆者としては，考え方がオートマトンに類似しているという
ニュアンスのつもりだったようです。ただ，「…の考え方を基
に」という言い方は，確かに紛らわしかったように思います。

……ニュアンス(´・ω・`)
もう一度読み直してみたら、こんなことが書いてました。

タイトルは「ヘビ」ですが、一般には「正規表現」と呼ばれる
分野に属する問題です。

あの・・・正規表現って思いっきり有限オートマトンと同じもの・・・
Perlの正規表現とかだったらマッチした回数とか取得できるんでしょうか。
そんなことを思い出しました。

This entry was posted on 金曜日, 7月 18th, 2008 at 9:39 AM and is filed under 雑記. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.