Path: katsu From: katsu@sra.co.jp (WATANABE Katsuhiro) Message-ID: Date: 24 Aug 1994 04:45:56 GMT Organization: Software Research Associates, Inc.,Japan In-reply-to: nitta@sra.co.jp's message of Tue, 23 Aug 1994 09:09:31 GMT Newsgroups: sra.tools Subject: Re: egrep Distribution: sra References: 記事 で nitta@sra.co.jp (Minoru Nitta) さんいはく > たとえば > % egrep '....... A' ;#(1) .が7個ある > はOKなのに、 > % egrep '^...... A' ;#(2) > だめです。 egrep の実装を気にせず、元々の正規言語の世界で考えると、'....... A' に 対応する決定性オートマトンの状態数は 10 です。同じく、'X...... A' に対 応するものの状態数も 10 です。両者とも . が増えても、状態数は長さに比例 するだけです。 根拠の薄い思いつきですが、これが egrep になると、文字列の途中に パターンが現れる場合もマッチするものと扱う必要がありますから、 'X...... A' の方は '.*X...... A' のようなものへ、 '....... A' は '.*....... A' へと変換されるのではないでしょうか。 '.*A...... A' のようなものの状態数は途中にはさまっている . の数で 指数的に増大しますが、'.*....... A' のようなものは '........* A' と 同等で状態数は長さに比例するだけです。 でも、文字列の途中のパターンを検出する方策が上のような素朴な戦略に なっているとは思えないし、^ が普通の文字と同じ扱いというのも 納得できないんですが。 -- 渡邊克宏＠四谷