トップ «前の日記(2008-10-10) 最新 次の日記(2008-10-12)» 月表示 編集

日々の流転


2008-10-11 [長年日記]

λ. Derivatives of Regular Expressions by Janusz Brzozowski

積読論文消化。 文字列の集合 R と有限の文字列 s に対して、R の s による微分を Ds := {t | st ∈ R} と定義する。正規表現の微分は正規表現になっていて、かつ正規表現を微分していって得られる正規表現は(等価なものを除けば)有限個で、それらを状態とする決定性有限状態オートマトンを正規表現から直接作ることが出来る。

関連