2008-10-11 [長年日記]
λ. Derivatives of Regular Expressions by Janusz Brzozowski
積読論文消化。 文字列の集合 R と有限の文字列 s に対して、R の s による微分を Ds := {t | st ∈ R} と定義する。正規表現の微分は正規表現になっていて、かつ正規表現を微分していって得られる正規表現は(等価なものを除けば)有限個で、それらを状態とする決定性有限状態オートマトンを正規表現から直接作ることが出来る。
関連
[ツッコミを入れる]
