覚え書き: 先読み・後読みを含む正規表現の数学的定式化

いかにも既知な気がしますが、ぱっと既存の議論が探せないのでとりあえず書き出してみます。 ※用語は独自のものです。また、証明・定義は厳密に検証しているわけではないので誤りがあるかもしれません。 この定義でカバーできること 先頭 ^ 末尾 $ 肯定先読み (?= ... ) 否定先読み (?! ... ) 肯定後読み (?<= ... ) 否定後読み (?<! ... ) この定義でカバーしないこと 選択の左右の優先度 (r1|r2 vs. r2|r1) 最長優先と最短優先の区別 (r* vs. r*?) 基本の正規表現 基本の正規表現は通常以下のように定義されます。 \Sigma はアルファベットで有限サイズとします。 文字リテラル a (a は文字 a \in \Sigma) 空文字列 \epsilon と連接 R_1R_2 (R_1, R_2 は正規表現) 空集合 \emptyset と