ーン 図 3 1 文字のパター 文字 パターン 2 ン 図 4 パターン結 パターン 1 パターン 2 パターン 1 図 5 パターンの尺 スするど遷移や、 : 頁に戻るど遷移を付けることで表現で 纜医しを表す ? 、十、 * は、対象となるパターンをバイバ らのパターンにも状態遷移できるようにします。 します ( 図 5 ) 。この場合も 6 遷移を利用することで、どち 選択も同様に構築でき、 2 つの状崟移図を並列に連結 ど遷移を利用します。 を連結するのに、文字を読み込まなくても状態遷移できる ( 図 4 ) 。このとき、最初のパターンと 2 番目のパターン 連結の場合は、 2 つの状態遷移図を連結するだけです 付けられたラベルが 1 文字のパターンとなります。 場合、図 3 のような状態遷移図として表現できます。辺に ますは 1 文字のパターンからです。 1 文字のパターンの ましよう。 できればよいのです。それでは、これらを個別にみていき でした。上記のそれぞれについて有限オートマトンか構築 ・ * はパターンの 0 回以 E の糸お区しを表す ・十はパターンの 1 回以 - E の区しを表す ・ ? は省略可能なパターンを表す 〕邇尺 (I) は 2 つのパターンのいすれかを表す ; 叫吉は 2 つのパターンの連続したものを表す ・ 1 文字はその文字自身を表す パターンとしての正規表現を構築する演算子の未は、 決定性有限オートマトンを欟薊勺に作成できるためです。 トンの構築法があり、パターンを構文角 i した結果から非 ターンを構築するための各演算子に対応する有限オートマ 性有限オートマトンに変換するという手順を踏みます。 様にます夬定性有限オートマトンを作成し、それを決定 のように作成したらよいでしよう。通常は、さきほどと同 60 図 6 図 7 図 8 図 9 A ? を用いたパタ ノヾターン 十を用いたパター / ヾターン ン * を用いたパターン 素直に変換したパター ノヾターン B C E D ン F K L ⑨望⑩、◎皂⑨、◎皂⑧ きます ( 図 6 ~ 8 ) 。 このように、正規表現を構文構造にもとづいてポトムア 冗長など遷移 定性有限オートマトンか得られます。 ップに変換することで、対応する状崟移図、つまり夬 すべてど遷移です。この状崟移図を、ど遷移で遷移可能 ります。図では明記されていませんが、ラベルのない辺は というパターンをこの方法で変換すると、図 9 のようにな a(blbd) *dad はさきはどの、 と、いたるところに冗長など遷移カ咐けられます。たとえ 前節のアルゴリズムにもとづいてパターンを変換する 図 1 のよう てもよいわけではありません。 ど遷移か長だからといって、変換の際にこれらを省い になります。 な状態を 1 つの状態にまとめて変換すると、 UNIX MAGAZINE 2000.10

インターフェイスの街角 図 9 4 本の線カに移動 図 8 ディスプレイを揺らすことによる高解像度表示 ( a ) 原画像 ロロロ ロ ロロ ロロロ 匚 ( b ) 表示される画像 知覚される画像 ディスプレイを動かさなくても、図 7 と同様の手法を 使えば高解像度の表示が可能になります。図 7 で、表示装 置を左に動かさすに静止させた場合の表示を図 9 に示しま す。ディスプレイが静止しているときは、パターンか変化 しながら右に移動することになります。しかし、人間の目 は移動に〕直するため、ユーザーには図 7 と同様に 4 本 の糸勦に移動するように見えます。 この効果を利用して画像を移動させながら表示すれは、 ディスプレイの解伽度以上のピクセルをもつ画像を表示さ せることができます。私は、この手法を PixeIDoubIer と呼んでいます [ 5 ] 。 図 10 は、ヒ、ツトマッフ。画像の表示に PixelDoubler を 応用した例です。 2 不頁の画像を交互にシフトさせながら 灰色のピクセルが表示されているように見えます。結果と 表示させることで、実際の解像度より細かい画像が表示で して、図 7 の最下行のように、ユーザーには 4 本の線が きます。 見えることになります。静止した 6 ピクセル幅の領域には 3 本しか線を表示できないので、ディスプレイを動かすこ 図 10 ー a が 226 x 76 ピクセルの原画像 10 です。これを とによって解像度が 33 % 向 - ヒしたことになります。 もとにして、 2 不頁の小さな ( 170 x 78 ピクセル ) 画像 II 同様の手法により、 10 x 10 ピクセルの領域に 14 x ( 図 10 ー b ) と 12 ( 図 10 ー c ) を用意します。 PixeIDoubIer 14 ドットのフォントを表示する手法を図 8 に示します。 は、 t = 0 において ( 0 , 0 ) の位置に II を表示し、 t こで、ディスプレイのピクセルは表示するフォントのピ において ( 0 , 0 ) の位置に 12 を表示します。また t = 2 クセルより 50 % 大きいにもかかわらず、ディスプレイを において ( ー 1 , 0 ) の位置に II を表示し、 t ー 3 におい 揺らしながら表示を変化させていけば、フォントの細い線 て ( ー 1 , 0 ) の位置に 12 を表示します。このように、 2 枚 も図 8 ー c のように認識できます。 の画像をシフトしながら交互に表示し続けていくと、ユー ザーには 10 と同じ解像度をもち、かっサイズが小さな画 このように、ディスプレイを動かしたり揺らしたりすれ 像が見えます ( 図 10 ー d ) 。 ll と 12 は 10 より少なし寸帯にし は、装置の解像度以、 . 」 : : の表示カ碍られます。 ( c ) 知覚される画像 153 UNIX MAGAZINE 2000.10

いつでも使えるインターネット 図 2 これて吠丈夫、 図 1 通常の TCP handshake クライアント クライアント ロ ロー ロ = 4 図 3 あれ ? クライアント ロー ・ ACK シーケンス番号は 0 トに そして、 SLII の tcpest はたしかにこのバケッ マッチします。しかし、 ・ SYN ピットがセットされている ・ ACK ビットがリセットされている ・ ACK シーケンス番号が 1 のバケットにはマッチしません。したがって、ほかの拒 否ルールにマッチしなければ、このバケットは素通りして しまいます。 さて、こからがおもしろいところです。通常の 3way handshake の 1 番目のノヾケットでは、 ACK シーケンス 番号に 0 がセットされます。しかし、いくつかの OS で 接続を確立できません ( 図 2 ) 。本当ならば、これでインタ は 0 でなくても TCP のセッションは確立します。 ーネットから内部の計算機を守れるはすです。 ちょっと難しいので図で説明しましよう。ます、通常 しかし、最初のバケットの ACK-SEQ に 1 を設定す の TCP handshake では、 3 つのバケットがクライアン ると、なんと SLII はそれを通してしまい、クライアント トとサーバーのあいだでやりとりされます ( 図 1 。詳しく とサーバーのあいだでコネクションか不寉立してしまいます は TCP/IP の解説書を参照してください ) 。 ( 図 3 ) 。 かえって話か難しくなって分かりにくいかもしれません ip filter が、要するに SLII では tcpest のルールを設定しても 懣未がなく ( 気休めにもなりません ) 、攻撃者から内部の計 のルールを SLII に設定すると、 1 番目のバケットがルー 算機を守れないということです。 タて捨てられるため、クライアントとサーバーは TCP の 4 tcpest 14 UNIX MAGAZINE 2000.10

インターフェイスの街角 図 5 液晶ティスプレイのサプピクセルの並び RGBRGBRGBRGBRGBRGBRGBRGBRGB RGBRGBRGBRGBRGBRGBRGBRGBRGB RGBRGBRGBRGBRGBRGBRGBRGBRGB RGBRGBRGBRGBRGBRGBRGBRGBRGB RGBRGBRGBRGBRGBRGBRGBRGBRGB ぎりでは RGB を別々に認識することはできません。 通常の用途では、 RGB のサプピクセルの組を 1 ピクセ ルとして扱っているわけですが、これを 3 個のサプピク セルとして独立に扱えれは解像度が 3 倍になるかもしれま せん。 0 0 図 1 の余将泉を図 5 と同様なサプピクセル表現です 0 0 0 0 0 0 9 9 0 0 0 0 6 6 3 3 0 0 6 6 0 0 9 9 9 9 9 9 9 9 9 9 0 0 9 9 0 0 0 0 9 9 0 0 0 0 9 9 0 0 9 9 0 0 9 9 0 0 9 9 9 9 #R G B 9 9 0 0 0 0 0 0 9 9 0 0 9 9 0 0 0 0 9 9 0 0 0 0 9 0 0 0 9 9 0 0 0 9 9 9 9 0 0 0 9 9 9 9 9 9 9 9 9 9 9 9 0 0 0 0 9 9 9 9 0 0 図 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 サプピクセル法による可泉 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 9 9 9 6 6 6 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 6 6 6 3 3 3 0 0 0 0 0 0 0 0 0 6 6 6 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 3 3 3 6 0 0 0 3 3 3 6 6 6 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 6 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 6 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ると、 RGBRGBRGB RGBRGBRGB RGBRGBRGB RGBRGBRGB RGBRGBRGB RGBRGBRGB のようになります。これを PPM (PortabIe PixMap) RGBRGBRGB RGBRGBRGB RGBRGBRGB 形式て表現すると以下のようになります。 # linel . ppm P3 6 9 9 サプピクセル法は、上に示したような通常のアンチ 0 0 3 6 ・ . 工 8 9 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 0 0 0 0 0 9 9 9 9 9 9 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 9 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 一方、図 2 のようにアンチ・エイリアシングを施しオ斗 . RGBRGBrgb rgbRGBRGB. RGBRGBRGB . RGBRGBrgb rgbRGBRGB. RGBRGBRGB . RGBRGBrgb rgbRGBRGB . RGBRGBRGB r 、 . と表記しています ) 。 線は以下のように表現できるでしよう ( 輝度に応して R 、 これを PPM 形式で表現すると以下のようになります。 # 1ine2. ppm イリアシング手法を使用する代わりに、各ピクセル内の RGB のサプピクセルを用いて解像度を高める技術です。 アンチ・エイリアシングではピクセル単位の輝度を制御し ますが、サプピクセル法では以下のようにサプピクセル単 位で輝度を制御します。 RGBRGBRGB GBRGBRGBR BRGBRGBRG RGBRGBRGB GBRGBRGBR BRGBRGBRG RGBRGBRGB GBRGBRGBR BRGBRGBRG 上から 3 行目の左端のピクセルは青 ( B ) になっていま す。白色の直線を表現するために青のピクセルを使うのは す ( 図 6 ) 。この画象を PPM 形式で表現すると以下のよ 定をおこなうと縁か滑らかできれいな白い斜線か得られま おかしいと思うかもしれませんが、実際にこのような色指 うになります。 # 1ine3 8 12 P3 9 P3 8 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 6 6 6 9 9 9 9 9 9 9 9 0 0 0 3 3 3 0 0 R G B 9 9 9 0 9 9 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 R G B 9 9 9 9 9 9 9 9 9 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 9 9 R G B 9 9 9 9 9 9 0 9 9 9 0 0 0 0 0 0 9 9 9 9 9 9 R G B 9 0 0 9 9 0 9 9 9 0 0 9 0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 R G B 0 0 0 0 9 9 9 9 9 9 9 9 9 9 9 9 R G B 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 UNIX MAGAZINE 2000 ユ 0 R G B 0 0 0 0 0 0 9 9 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 151

個人の常時接続環境を考える ( 4 ) 図 7 RTA52i での認証 ー - > ユーサー名とパスワドを入力してくだ & 、。 1 、 168.01 サイト YAMAHA-RT [ lc 粤れ記 m ⅶ s ] ュサー名 パスワード をのパスワ陸保存る 初トワクを新スワ , ドの第カ・舞気第 設定したパスワードを入力 OK もクリックしなければならす、かなり不便てす。さらに、 ウサでアクセスすると、図 6 の画面が表示されて、パスワ フィルタの内容を編集するインターフェイスがないので、 こでノヾスワードを設 ードの設定を促されます。そして、 追加したフィルタの一部を修正したいときは、いったんそ 定しなければ次の画面に進めませんし、何も設定できませ れを削除し、新たに」助日しなけ川まならないようです。ひ ん。ちょっと強引な手段ですが、セキュリティ面からみ どく不便です。 ると望ましい方法だと思います。 パスワードを設定すると、図 7 のウインドウが表示さ Web インターフェイスでフィルタを登録する場合は、 れます。ここでは、さきほど設定したパスワードを入力し フィルタ番号には 80 から 99 までの数字を割り当ててく ます。 ださい。それ以外の番号 ( 20 番など ) のフィルタも登録 次はフィルタの設定です。 Web プラウサで、、かんたん できますが、 1 ~ 79 番と 100 番はシステムて予約されて 成疋 " →、、システム管理 " →、、フィルタ設定 " を順番にク いるので、あまりお勧めできません。予約されている番号 リックすると、図 8 のような画面か表示されます。 を勝手に使ったりすると、突然肖えてなくなったり、別の フィルタルールで上書きされるかもしれません。 このページは、 フィルタを削除するには、「フィルタ定義の削除」のと ・フィノレタ : 定義の設定 ころでフィルタ番号を選び、 [ 削除 ] ボタンをクリックし ・フィルタ定義の追加 ます ( 図 9 ー b ) 。 ・フィルタ定義の削除 「フィルタリングのセット」では、 PPP や LAN のイン ・フィルタリングのセット ターフェイスに設疋するフィルタをチェックポックスで 選べるようになっています ( 図 9 ー c ) 。一見するとそれなり の 4 つのセクションに分かれています。 にイ甦リそうですが、適用するフィルタの順番を指定するこ 最初の「フィルタ定義の設定」のところには、現在シ とはできません。おそらく、番号の小さいはうから順に適 ステムに登録されているフィルタのリストか表示されてい 用するように設定されるのではないかと思われますが、確 ます。 証はありません。順番を制御したいときは、コマンドライ 次の「フィルタ定義の追加」では、新規フィルタルー ン・インターフェイスから入力するしかなさそうです。 ルを登録します ( 図 9 ー a ) 。画面を見ると、 GUI で簡単に 設正できそうに思えます。本当にそうならいいのですか、 こまでにみてきたように、すくなくともフィルタの設 そんなに都合よく話は進みません。よくよく見ると、前述 定に関しては Web インターフェイスはかなり不便です。 したフィルタルールの項目に対応するテキストボックスが コマンドライン・インターフェイス きれいに並んでいるだけです。つまり、コマンドライン ます、パスワードの設定去を紹介します ( 図 10 ) 。 インターフェイスで入力するのと大差ありません。必要な 項目をすべて書いたら、 Cj 砌日 ] ボタンをクリックします。 パスワードが設定されていない RTA52i に telnet ク 複数のフィルタを追加するときは、 [ 追加 ] ボタンを何回 ライアントでアクセスすると、最初にパスワードの入力を 19 UNIX MAGAZINE 2000 ユ 0

図 10 ど多を省いた十パター B A 図 11 ど遷移を省いたパターン本 C B A ン A B C D E F G 図 12 ど遷移を省かず変換したパター ン というパターンを考えてみましよう。冗長など遷移を省く ど遷移を省きながらパターン全体を描くと図 というパターンは図 10 のように表せるでしよう。 同様に、 UNIX MAGAZINE 2000 ユ 0 いうガ召介されています。 子にはど遷移を用いず、 * 演算で逆向きのど遷移を内倶状態に付けると 2 ここに示した変換以タ ) ガ去もあります。参考文献 [ 1 ] では連結の演算 た。しかしど遷移があると、かならず非決定性有限オート 変換時に付けられる 8 遷移が重要なことは分かりまし NFA から DFA への変換 はできないたいへん重要なものです 2 。 なるためです。冗長にみえるど遷移ですが、省略すること に遷移すると、 ? による A から H への辺を利用できなく 文字の文字列 a は受理できません。これは、一度状態 B ると、図 12 のようになります。この状態遷移図なら、 1 そこで、ど遷移を省かずにさきはどのパターンを変換す 列 a とは一数しないため、これでは困ります。 遷移できてしまいます。パターン ( a + b ) ? は 1 文字の文字 り開女幇大態 A に戻り、さらにど遷移により受理状態 C に 女大態 A から文字 a により状態 B に遷移し、ど遷移によ て a という 1 文字の文字列を受理してしまうのです。開 しかし、この状態遷移図には間題があります。入力とし 11 のようになります。 プログラミング・テクニック マトンとなってしまいます。前述したとおり、実際の処理 では決定性有限オートマトンとして扱うほうか圧倒的に有 利です。そこで、今度は非決定性有限オートマトンを決定 性有限オートマトンに変換するガ去をみていきましよう。 変換ガ去はいくつかありますが、そのなかでも間的で分 かりやすい部分集合構去を紹介します。 イ歹地として、図 9 の夬定性有限オートマトン似ード、 NFA) をとりあげます。このオートマトンでは、開女幇大態 の A から文字 a を読み込むだけで、 B 、 C 、 D 、 E 、 G 、 L 、 M の 7 つの状態に状当多できます。具イ勺には、 NFA の状態の集合を決定性有限オートマトン ( 以下、 DFA) の 61 L 、 M の 8 つの状態に遷移可能です。また、 NFA の状 ります。ど遷移も含めると、状態 C 、 D 、 E 、 F 、 G 、 K 、 E から文字 b による状態遷移をおこなうと、状態 F に移 ます文字 b による状態遷移を調べてみましよう。 NFA の 状態からは、文字 b と文字 d による状も崟移か可能です。 次は追加した状態 BCDEGLM の処理です。これらの る処理はこれて終了です。 文字では A からは状崟移できないので、状態 A に関す に新たに BCDEGLM という状態を追加します。ほかの L 、 M の 7 つの状態に状態遷移できます。そこで、 DFA 字 a を読み込むと、前述したように B 、 C 、 D 、 E 、 G 、 態遷移が可能なのは文字 a を読み込んだときだけです。文 としては A だけがあります。 NFA に戻ると、 A から状 これを伊題に適用してみましよう。現在、 DFA の状態 ありません。 集合が DFA に追加されていれば、さらに」助日することは ます。もちろん、 NFA の状態集合として、すでに同一の すべてを集合としてまとめたものを DFA の状態に追加し る状態から状態遷移可能な状態を調べます。そして、その に対応する NFA の状態集合について、その集合に含まれ ないます。入力に含まれる文字ごとに、 DFA のある状態 次に、 DFA のすべての状態について以下の処理をおこ A か帽始状態となります。 ます。例題には A からのど遷移はないので、 DFA でも 始状態 A からど遷移のみで到達可能な状態集合を言算し た状態集合を表す DFA の状態を作成します。つまり、開 態からど遷移のみで到達可能な状態集合を計算し、得られ 実際の処理をみていきましよう。ます、 NFA の開始状 状態に対応づけることでオートマトンを構築します。

連載 / 遠隔オフィスとの接続ーの 図 3 課金単イ寺間方式 ・・課金単位時間・ 回線切断 ・課金単位時間・ ・課金単位時間 監視時間 余裕時間 監視時間 余裕時間 監視時間 余裕時間 通信開始 図 4 課金単イ立時間方式の言聢例 図 2 は、もっとも簡単な単純トラフィック監視方式の isdn disconnect policy 2 設定例です。 1 行目の、 isdn disconnect interval time 180 20 2 isdn disconnect policy れ 課金単位時間方式 は、通信の自動切断方式を選ぶコマンドで、 図 3 は課金単イ間方式の説明図です。 RT は課金単位 時間の直前の数不少間を監視し ( 図の、、監宅期間 " ) 、そのあ ・れが 1 なら単純トラフィック監視方式 いだにバケットカ毓れなけ川ま通信を切断します。ただ、 ・れが 2 なら課金単位日判方式 RT が、、切断しよう " と判断してから実際に回線か切断さ れるまでには時間がかかるので、そのぶんを、、余ネ卻間 " として設定できるようになっています。すなわち、課金単 位時間からさかのは、って、 課金単時間一 ( 監視翩間十余裕日判ゆ ~ 課金単イ立日判一余 のあいだ、バケットを監視します。 は、監ネ期間を watch-time に設疋するコマンドです。監 この方式は屯トラフィック監視方式よりも通信料・を低 彳期間は 0.1 秒単位の秒数で指定してください。囮観 c ん - く抑えられる可能性があります。 RT の、、かんたん設疋 ′し′亠・ " 励れ e に。仕を指定すると設定か解除されます。 のデフォルトは、課金単位時間方式になっています。 図 2 の例では監視時間を 120.1 秒 3 にしていますが、 図 4 は、簡単な課金単位日判り方式の設定例です。 1 行目 c ん me を省略した場合には監ネ期寺間が 60 秒になり の監視方式の選択についてはすでに説明したのて省略しま ます。 す。 2 行目の、 この設定は、入力と出力の両方向のバケットを監視しま すが、次のコマンドを使えば入力バケットだけ、あるいは isdn disconnect interval 社れを - 厖 ? 7 ~ e 囮佖 c ん - me s 〃佖 7 、 e - me 出力バケットだけを監視することもできます。 は、課金単位時間方式てイ吏用する 3 つの日判窈旨定で、 入力バケットの監ネ期寺間を設定するコマンド isdn disconnect input time 社 1 佖 tc ん - 7 〃 e ・・ bit-time : 課金単イ寺間 ・ watch-time : . 監視日 出力バケットの監ネ期寺間を設定するコマンド ・夘℃ - me : 余裕日閉 isdn disconnect output time 佖 tc ん - 7 e をそれぞれ 0.1 秒単位の秒数て指定します。 それぞオ L 、観 c ん - れ e を省略した場合には、監ネ寺間 これらの 3 つの時間の値は省略することもできます。そ が 120 秒に設定されます。 の場合のデフォルト値は、 3 1 科末岡の単位で指定できることを示すために半端な移数にしてあります 課金単位時間 : 180 秒 ( 3 分 ) が、 120.1 秒でも 120 秒でも実質的な違いはありません。 - 三 2 行目の、 isdn disconnect time watch-time 51 UNIX MAGAZINE 2000.10

プログラミング・テクニック 決定性有限オートマトン 図 2 BC D 図 1 非決定性有限オートマトン ど ( し . ど ・ 0 .0 ・ 0 開 始 d BDE b d a a G F E D B A 開始 のように、 1 つの文字 ( とど遷移 ) により状軋も崟移可能なす べての状態をイ寺しておきます。そして、次の文字を読み 込んだときに、イ尉寺しているすべての状態から可能な状態 有限オートマトンを使うと、ある文字列が正規表現で書 遷移をヾることで、正しく受瓔伏態まて移行できます。 かれたパターンと一致するかどうかを調べることができま しかしこのガ去では、状態遷移をおこなうたびにど遷移 す。たとえは、次のようなパターンを考えてみましよう。 で遷移可能な状態を調べる必要があり、状態の集合を扱わ なければならないため、処理は面倒になります。そこで、 a()l bd)*dad もっと簡単な処理去として、この夬定性有限オートマト このパターンは、ます a があり、その後ろに b か bd ンを決定性有限オートマトンに変換するガ去があります 1 。 のいすれかを 0 回以上繰り返したものカき、さらに dad 上記の夬定性有限オートマトンを決定性有限オートマト がつながったものです。したがって、図 1 のような状崟 ンに変換すると、図 2 のような状態遷移図か得られます。 移図て表せる非決定性有限オートマトンで認識できます。 こちらの場合にはど遷移がなく、ある状態から出ている このパターンに -- - ・致する、 辺のラベルに共通部分がなくなっています。 abdbdad 状態名は図 1 と同しものを使っています。複数の状態名 という入力なら、以下のような過程を経て受伏態まて状 からなる BD などは、図 1 での複数の状態のいすれかに 当多します。 あることを表します。この決定匪有限オートマトンでは、 ど b d a d a b d 状態遷移は次のようになります。 A → B → C → D → B → D → E → F → G a b B d B b B d B a d こで作成したのは夬定生のオートマトンな しかし、 A → B → C → D → C → D → F → G D E D E ので、途中でとるべき辺を誤ると、同し入力なのに状崟 移する先がなくなってしまいます。たとえば次のような状 さきはどの夬定性有限オートマトンの場合とまったく 態遷移をした場合、途中で状態遷移するための辺がなくな 同じにみえるかもしれませんが、 BCD などの文字列か馥 ります。 数の状態ではなく 1 つの状態を表している点が異なりま ど b d a b d す。決定性有限オートマトンでは、状態遷移の最中に選べ A → B → C → D → B → C → D → ? ? ? る〕尺肢はかならす 1 つしかありません。 この場合、 2 度目の状態 B からの文字 b による遷移で 状態 C に遷移したため、あとで遷移先がなくなってしま いました。 このように、遷移先がなくなってしまうことがあとか 入力がパターンに一致しているかを調べるには、決定性 ら判明する場合もあるため、夬定性有限オートマトンを 有限オートマトンを構築して、それが入力を受理するかど 使って文字列の受理を十ヾるときには、すべての場合を調 うかを謌べるのか簡単です。では、パターンカ甘旨定された べながら処理を進める必要があります。具イ勺には、 ときにそのパターンを表す決定性有限オートマトンはど b B d B b B d B a d 1 任意の共定性有限オートマトンは、かなら生有限オートマトンに → C → D → C → D → F → G A → 変換できます。 D E D E F E BD A 正規表現とオートマトン 正規表現からの NFA の作成 B D 59 UNIX MAGAZINE 2000.10

部分集合構成法により得られた DFA 図 13 態 G からは、文字 b による状態遷移で態 H 、 1 に遷移 できます。 BCDEGLM に含まれるほかの状態からは、文 字 b により状態遷移する辺は出ていないので、ここで得ら れた状態の集合を表す CDEFGHIKLM を新たに DFA の状態として追加します。 状態 BCDEGLM からのもう 1 つの遷移は、文字 d に 表 1 状態多表 よるものです。これは、 NFA の状態 M から文字 d によ ラ′くノレ り状態 N に遷移し、さらにど遷移により状態 O に遷移し 0 1 ます。そこで、 DFA の新たな状態として NO を追加し BCDEGLM 1 ます。 CDEFGHIKLM 2 CDEGJKLMNO 3 5 この段階で、 DFA には 4 つの状態 (A 、 BCDEGLM 、 4 NO 5 CDEFGHIKLM 、 (O) か含まれます。最初の 2 つの状 PQ 5 態から出ている辺については調べたので、次は 3 番目の状 6 態 CDEFGHIKLM の処理です。この状態からも文字 b これらを整理すると、図 13 のような状態遷移図カ碍ら と文字 d による状崟移が可能です。文字 b による状態遷 れます。この状崟移図は、図 2 に示した決定性有限オー 移では、 C 、 D 、 E 、 F 、 G 、 H 、 I 、 K 、 L 、 M の 10 の状態 トマトンにたいへんよく似ています。状態名を無視すれば に遷移可能です。これらを表す状態は CDEFGHIKLM まったく同し状当多図です。部分集合構去により、正 となりますが、これはすでに DFA にあるため追加は不要 しく夬定性有限オートマトンを決定生有限オートマトン です。一方、文字 d による状態遷移では、 C 、 D 、 E 、 G 、 に変換できることがこれで分かります。 J 、 K 、 L 、 M 、 N 、 O の 10 の状態に遷移可能です。そ こで、これらの状態集合を表す CDEGJKLMNO を、 5 番目の状態として DFA に追加します。 4 番目の状態 NO からは、文字 a による状崟移のみ これまでは、状崟移図を使って有限オートマトンを表 が可能で、遷移する先は状態 P 、 Q です。 DFA には 6 番 現してきました。これを言 1 算機で処理するには、日算機か 目の状態として PQ を j 助日します。 扱いやすい形式に変換して一尉寺しなけれはなりません。 5 番目の状態 CDEGJKLMNO からは、文字 a 、 b 、 の点について考えてみましよう。 d による状当多が可能です。文字 a による状崟移では もっともストレートな去としては、各状態に番号を割 状態 PQ となり、 DFA への追加は必ありません。文字 り当て、状崟移には、現在の状態と入力文字から次の状 b による状態遷移では状態 CDEFGHIKLM となり、こ 態を指すような 2 次元の整数型配列を用いるというものが れも DFA への追加は必要ありません。文字 d による状 あります。この方法でさきほど変換した DFA を表現する 態遷移では状態 NO となり、やはり DFA への追加は不 と、表 1 のようになります ( 入力文字としては、状態遷移 要です。 図に現れる a 、 b 、 d だけを扱っています ) 。 6 番目の状態 PQ からは、文字 d による状態遷移が可 能です。文字 d による状態遷移では状態 R となり、 DFA 表 1 の遷移先の値として一 1 カ甘旨定されているものは、 の 7 番目の状態として追加します。 遷移すべき状態がない、つまりその文字を入力として受理 できないことを示します。 状態 R からは、 NFA では辺が出ていないので、これ で変換は終了です。 NFA の開女幇大態の A を変換した状態 この例では、アルファベット集合 ( 入力に現れる文字の A を、 DFA の開始状態とします。また、 NFA で受理状 集としてごく小さなものを使ったのでとくに間題はあ 態の印が付けられた状態を含む DFA の状態は、やはり受 りませんが、大きな集合 (C 言語て表現可能なすべての文 理状態とします。今回の例では状態 R のみです。 字を含むなど ) の場合は、状態遷移表も巨大になってしま CDEFGHIKLM BCDEGLM CDEGJKLMNO 開始 NO A 理 受 1 -4 っ 0 4 1 、 6 1 上 1 亠っワ 1 っ 4 1 亠 11 1 亠 DFA の計算機上での表現 62 UNIX MAGAZINE 2000.10

0 図 7 6 ピクセル幅で 4 本の線を表示 白黒の誌面では上交は不可能ですが、液品ディスプレイ 原画像 上で図 1 と図 2 、図 6 の 3 者を上交すると、明らかに図 6 力一番きオ・しいな滷線に見えます。 サプピクセル法の限界 サプピクセル法は興味架い技術ですが、どんな場面でも 有効なわけではありません。前例の場合はたしかに効果が ありますが、以下の間題があります。 ・カラー画像には適用できない モノクロ画像の表示には効果がありますが、各色に対応 した画素の数は変わらないので、単色や暗い色の画像で は効果がありません。 ・細い線の両端がにじんで見える サプピクセル法で 4 / 3 ピクセルの幅をもっ白い糸泉を 引くと、以下のサプピクセルが ON になります。 GBRG GBRG GBRG GBRG 液品ディスプレイ上でこの画像を石忍すると、緑の要素 がほかよりも多いため、左右の端カ彖がかって見えてし まいます。輝度を左右に拡散させれば、このような望ま しくない発色現象を低咸することはできますが、画像は はやけてしまいます。 水平方向の解像度にしか効果がない 通常、液品ディスプレイのサプピクセルは横方向に並ん でいるため、水平方向の解像度しか向上しません。多く の漢字は横線の密度のはうか泉よりも細かいので、サ プピクセル法を用いて漢字を表示するときは液品ディス プレイを横にしたほうか踝的です。 ・液品ディスプレイ以外では効果がない サプピクセル法では、水平方向に並んだ RGB サプピ クセルを正確に ON/OFF する必要があります。 CRT はピクセル位置の正確さに欠けるため、目立った効果は 得られません。 ClearType がサプピクセル法と類似した技術かどうか は不明ですが、この手法に似たものだとすると、たしかに 有用ではあるものの、、、まったく新しい技術 " とか、、解像 このとき、ェ = 3 の位置では黒いピクセルが、ェ = 5 の 位置では点滅するピクセルが表示されます。タイムスライ 度を 3 倍にする " というのはちょっと言いすぎかもしれま スが十分に小さければ、ユーサーにはェ = 5 の位置には せん。 ロロロロロ x = 0 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 ロロロロ ロロロロ 匚 知覚される画像 PixelDoubler アンチ・エイリアシングやサプピクセル法のような技 術を使うと、たしかに画面表示は美しくなりますが、ハー ドウェアの解像度を超える表示が可能なわけではありませ ん。しかし、重丿を利用す川ま、ハードウェアの解像度以 上の表示か得られる場合もあります。 テレピでがきれいに見えていても、画面を停止させ るとノイズや解像度が気になることがあります。これは、 画面か動いているとノイズがあまり気にならないというこ ともありますが、重丿では静止画より高い解像度か得られ るのも一因です。 測のほうが静止画より高い解像度か得られることを示 すため、表示装置を移動させながら画面を変化させてい き、 6 ピクセル幅の領域に 4 本の線を表示する例をもと に説明します ( 図 7 もあわせて見てください ) 。 ディスプレイを 1 タイムスライスごとに半ドットすっ 左に動かしながら、次のように表示していきます。 ーローーローロ ローーローーロ t = 2 152 UNIX MAGAZINE 2000 ユ 0