Path: katsu
From: katsu@sra.co.jp (WATANABE Katsuhiro)
Message-ID: <KATSU.94Aug24134557@sran205.sra.co.jp>
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: <Cux8FF.Du9@sranha.sra.co.jp> <Cuz3sM.1o0@sranha.sra.co.jp>
	<CuzDE4.AyL@sranha.sra.co.jp>

記事 <CuzDE4.AyL@sranha.sra.co.jp> で
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' と
同等で状態数は長さに比例するだけです。

でも、文字列の途中のパターンを検出する方策が上のような素朴な戦略に
なっているとは思えないし、^ が普通の文字と同じ扱いというのも
納得できないんですが。

--
渡邊克宏＠四谷