正規表現って結局何なのさ？〜エンジニアのためのコンピューターサイエンス入門〜

正規表現って a s i t a h W ? n 何 結局 なのさ？ o i s s e r p x E r a ul g e R 〜エンジニアのためのコンピューターサイエンス入門〜 iOSDC2022

自己紹介

自己紹介 岐阜県在住 フリーランスエンジニア iOSDCでの登壇は3回目 エンジニアと人生コミュニティに生息 趣味で鉄を作っています @ta̲ka̲tsu

用語

用語 アルファベット 「1文字」のこと アルファベット集合 Σ a b アルファベットの有限集合 ※今回は特に断りのない限り Σ = {a, b} とする

用語 文字列 アルファベットを0個以上 並べたもの 文字列集合 文字列全てからなる集合 Σ* ε a b aa ab ba bb aaa aab aba abb ⋯ aaaa aaab aaba ⋯ ⋯

用語 文字列(系列) アルファベットを0個以上 並べたもの 文字列集合 文字列全てからなる集合 ※ ε は空文字列を表す Σ* ε a b aa ab ba bb aaa aab aba abb ⋯ aaaa aaab aaba ⋯ ⋯

用語 文字列の連接 w1 = a1a2⋯am w2 = b1b2⋯bn (a1, a2, ⋯am ∈ Σ) (b1, b2, ⋯bn ∈ Σ) のとき、文字列同士の連接 w1 ⋅ w2 を w1 ⋅ w2 = a1a2⋯amb1b2⋯bn とする 特に w ⋅ ε = w ε⋅w=w

用語 連接の演算子は省略されることが多い w1 ⋅ w2 = w1w2 n また文字列 w を n 個連接したものは w と書くことがある

用語 言語 文字列集合の一部 (部分集合) ⋯ Σ* L ⋯ ※空集合も言語

導入

導入 https://developer.apple.com/wwdc22/sessions/

• https://developer.apple.com/wwdc22/sessions/

導入 Σ* 正規表現 言語を決定する表現の１つ 正規表現 r で定まる言語を L(r) と書くことにする r = a(a | b) * L(r) a aa ab aaa aab aba abb ⋯

導入 文字列 w が正規表現 r に Σ* マッチする L(r) ⟺ 文字列 w が言語 L(r) に 含まれる (w ∈ L(r)) ⋯ w ⋯

導入 疑問 どんな言語 L に対しても それに対応する 正規表現はあるか？ ? ⋯ Σ* L ⋯

🙅

導入 正規言語 ある正規表現で 表現できる言語 ⋯ Σ* L ⋯ r

導入 例えば n n 言語 L = {a b | n ∈ ℕ} は正規表現では 表現できない!! Σ* ⋯ L ε ab aabb aaabbb aaaabbbb ⋯

導入 ※本日の内容は「完全一致」のみを取り扱います

正規表現の定義

正規表現の定義 アルファベット１文字は正規表現 Σ* L(a) L(a) = {a} a ⋯

正規表現の定義 ε は正規表現 Σ* L(ε) L(ε) = {ε} ε ⋯

正規表現の定義 ∅ は正規表現 Σ* L(∅) L(∅) = {} ⋯

正規表現の定義 選択 r1, r2 が正規表現ならば r1 | r2 も正規表現 L(r1 | r2) = L(r1) ∪ L(r2) Σ* L(r1) L(r2) L(r1 | r2) ⋯

正規表現の定義 連接 r1, r2 が正規表現ならば r1 ⋅ r2 も正規表現 L(r1 ⋅ r2) = {w1 ⋅ w2 | w1 ∈ L(r1), w2 ∈ L(r2)} 例：L(r1) = {aa, bb}, L(r2) = {ab, ba}のとき L(r1 ⋅ r2) = {aaab, aaba, bbab, bbba}

正規表現の定義 繰り返し r が正規表現ならば r * も正規表現 L(r*) = {ε} ∪ L(r) ∪ L(r ⋅ r) ∪ L(r ⋅ r ⋅ r)⋯ 例：L(r) = {ab, ba} のとき L(r*) = {ε, ab, ba, abab, abba, baab, baba, ababab, ⋯}

正規表現の定義 ※演算子の優先順位は * 、⋅ 、| の順に高いものとする また、連接の記号 ⋅ は省略されることが多い 例： a | bc * は a | (b ⋅ (c*)) を意味する

正規表現の定義 選択と連接の結合律 (r1 | r2) | r3 = r1 | (r2 | r3) = r1 | r2 | r3 (r1 ⋅ r2) ⋅ r3 = r1 ⋅ (r2 ⋅ r3) = r1 ⋅ r2 ⋅ r3 選択の交換律 r1 | r2 = r2 | r1

正規表現の定義 分配律 r1 ⋅ (r2 | r3) = (r1 ⋅ r2 | r1 ⋅ r3) (r1 | r2) ⋅ r3 = (r1 ⋅ r3 | r2 ⋅ r3)

正規表現の定義 その他の性質 r|r = r (r*) * = r * ε⋅r=r⋅ε=r ∅* = ε ∅⋅r=r⋅∅=∅ r1 ⋅ (r2 ⋅ r1) * = (r1 ⋅ r2) * ⋅r1 ∅|r = r|∅ = r

正規表現の定義 言語を決定するその他の仕組み 決定性有限オートマトン(DFA) 非決定性有限オートマトン(NFA) 一般化非決定性有限オートマトン(GNFA)

正規表現の定義 言語を決定するその他の仕組み 決定性有限オートマトン(DFA) 非決定性有限オートマトン(NFA) 一般化非決定性有限オートマトン(GNFA) 正規表現と全く同じ表現能力を持つ！

Deterministic 決定性 有限オートマトン Finit Automaton

決定性有限オートマトン(DFA) a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) 状態(有限個) a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) 初期状態 a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) 受理状態 a, b b a q1 a q2 q3 b ※受理状態は複数あっても良い(無くても良い)

決定性有限オートマトン(DFA) 状態遷移 a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) 状態遷移 a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) 状態遷移 a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) 状態遷移 a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) abaab a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) abaab a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) abaab a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) abaab a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) abaab a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) abaab a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) a b a a b は受理される a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) ababa a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) ababa a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) ababa a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) ababa a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) ababa a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) ababa a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) a b a b a は受理されない a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) a a という部分列を含む文字列を受理する a, b b a q1 a q2 b q3

決定性有限オートマトン(DFA) a a という部分列を含まない文字列を受理する a, b b a q1 a q2 b q3

Nondeterministic 非決定性 有限オートマトン Finit Automaton

非決定性有限オートマトン(NFA) b q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b アルファベットに対する 遷移が無くても良い q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b アルファベットに対する遷移が 複数あっても良い q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ε 遷移があってもよい (入力がなくとも遷移できる) q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b 非決定性有限オートマトンでの 「受理」とは？ q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b 非決定性有限オートマトンでの 「受理」とは？ q2 ε b q1 a 受理状態に至る 遷移の列が「存在する」こと a b q3 a

非決定性有限オートマトン(NFA) b ababa q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababa q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababa q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababa q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababa q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababa q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababa q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b a b a b a は受理される q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababb q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababb q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababb q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababb q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababb q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababb q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b ababb q2 ε b q1 a a b q3 a

非決定性有限オートマトン(NFA) b a b a b b は受理されない q2 ε b q1 a a b q3 a

DFAとNFAの同値性

DFAとNFAの同値性 決定性有限オートマトンは 非決定性有限オートマトンの一種 a, b b a q1 a q2 b q3

DFAとNFAの同値性 決定性有限オートマトンは 非決定性有限オートマトンの一種 a, b b a q1 a q2 b q3 決定性有限オートマトンで表現できる言語は 非決定性有限オートマトンで表現できる

DFAとNFAの同値性 b q2 ε b q1 a a b q3 a

DFAとNFAの同値性 b q2 ε {q1, q2} b q1 a a b q3 a

DFAとNFAの同値性 b a {q1, q2} {q3} q2 ε b q1 a a b q3 a

DFAとNFAの同値性 b a {q1, q2} {q3} q2 ε b q1 a a b q3 b a

DFAとNFAの同値性 b a a {q1, q2} {q3} q2 ε b q1 a a b q3 b a

DFAとNFAの同値性 b a a {q1, q2} b ε {q3} b {q2} q2 b q1 a a b q3 a

DFAとNFAの同値性 b a a {q1, q2} b ε {q3} a b {q2} q2 b q1 a a b q3 a

DFAとNFAの同値性 b a a {q1, q2} b b ε {q3} a b {q2} q2 b q1 a a b q3 a

DFAとNFAの同値性 b a a {q1, q2} b b ε {q3} a b {q2} q2 b q1 a a b q3 a

DFAとNFAの同値性 b a a {q1, q2} b b ε {q3} a b {q2} NFAと等価なDFA q2 b q1 a a b q3 a

正規表現とNFA

正規表現とNFA 任意のアルファベット a 正規表現 a

正規表現とNFA 任意のアルファベット a 正規表現 NFA a a

正規表現とNFA 空文字 ε 正規表現 ε

正規表現とNFA 空文字 ε 正規表現 ε NFA

正規表現とNFA ∅ 正規表現 ∅

正規表現とNFA ∅ 正規表現 ∅ NFA

正規表現とNFA 選択 正規表現 r1 r1 | r2 ⋯ r2 ⋯

正規表現とNFA 選択 正規表現 r1 | r2 NFA ε r1 ⋯ ε ε r2 ⋯ ε

正規表現とNFA 連接 正規表現 r1 ⋅ r2 r1 ⋯ r2 ⋯

正規表現とNFA 連接 正規表現 r1 ⋅ r2 NFA ε r1 ⋯ ε r2 ⋯ ε

正規表現とNFA 繰り返し 正規表現 r* r ⋯

正規表現とNFA 繰り返し 正規表現 r* NFA ε r ⋯ ε

正規表現とNFA 決定性有限オートマトン(DFA) 非決定性有限オートマトン(NFA) 正規表現

正規表現とNFA 決定性有限オートマトン(DFA) 非決定性有限オートマトン(NFA) 正規表現

正規表現とNFA 決定性有限オートマトン(DFA) 非決定性有限オートマトン(NFA) 正規表現

正規表現とNFA 決定性有限オートマトン(DFA) 非決定性有限オートマトン(NFA) ？ 正規表現

Generalized Nondeterministic 一般化非決定性 有限オートマトン Finit Automaton

一般化非決定性有限オートマトン(GNFA) b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) 状態遷移に正規表現を許したもの b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) 非決定性有限オートマトンは 一般化非決定性有限オートマトンの一種 b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) bbaba b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ b ⋅ a ⋅ ba b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ b ⋅ a ⋅ ba b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ b ⋅ a ⋅ ba b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ b ⋅ a ⋅ ba b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ b ⋅ a ⋅ ba b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ b ⋅ a ⋅ ba b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a は受理されない？ b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ ε ⋅ ba ⋅ b ⋅ a b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ ε ⋅ ba ⋅ b ⋅ a b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ ε ⋅ ba ⋅ b ⋅ a b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ ε ⋅ ba ⋅ b ⋅ a b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ ε ⋅ ba ⋅ b ⋅ a b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ ε ⋅ ba ⋅ b ⋅ a b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a = b ⋅ ε ⋅ ba ⋅ b ⋅ a b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b b a b a は受理される！ b a* b q1 q2 ab | ba q3

一般化非決定性有限オートマトン(GNFA) b a a a b は受理されない b a* b q1 q2 ab | ba q3

GNFAと正規表現の 同値性

GNFAと正規表現の同値性 どんな正規表現もGNFAで表せることは明らか 正規表現 GNFA r r

GNFAと正規表現の同値性 どんな正規表現もGNFAで表せることは明らか →どんなGNFAも正規表現で表せることを示せば良い GNFA 正規表現 b a* b q1 q2 ab | ba q3 ？

GNFAと正規表現の同値性 GNFA … … … …

GNFAと正規表現の同値性 新しい開始状態を追加し、 開始状態への遷移がないようにする … … … … ε

GNFAと正規表現の同値性 新しい受理状態を追加し、受理状態を一つにする 受理状態からの遷移がないようにする … … ε … ε ε …

GNFAと正規表現の同値性 開始状態と受理状態以外の状態を 等価性を保ったまま削除していく … … ε … ε ε …

GNFAと正規表現の同値性 削除する状態に着目 qr

GNFAと正規表現の同値性 削除する状態に遷移する状態を列挙 p1 qr … p2

GNFAと正規表現の同値性 削除する状態から遷移する状態を列挙 p1 q1 p2 q2 … … qr

GNFAと正規表現の同値性 自身への遷移 p1 q1 p2 q2 … … qr

GNFAと正規表現の同値性 p1 r3 r1 r5 p2 q2 … qr … r2 r4 q1

GNFAと正規表現の同値性 削除する状態に遷移する状態と 削除する状態から遷移する状態のペアを考える p1 r3 r1 r5 p2 q2 … qr … r2 r4 q1

GNFAと正規表現の同値性 削除前と等価な状態遷移 p1 r3 r1 r5 p2 q2 … qr … r2 r4 q1 p1 r1 ⋅ r3 * ⋅r4 q1

GNFAと正規表現の同値性 すべてのペアの組み合わせに適用し 削除が完了する r1 r2 ⋅ r3 * ⋅r4 q2 p2 q2 p2 … r5 q1 r1 ⋅ r3 * ⋅r5 … qr p1 … r2 r4 q1 r1 ⋅ r3 * ⋅r4 r2 ⋅ r3 * ⋅r5 … p1 r3

GNFAと正規表現の同値性 初期状態と受理状態だけになるまで 状態の削除を繰り返す GNFA … … … … 等価なGNFA r

GNFAと正規表現の同値性 そのラベルが元のGNFAと等価な正規表現 GNFA … … … … 等価なGNFA r

GNFAと正規表現の同値性 決定性有限オートマトン(DFA) 非決定性有限オートマトン(NFA) 正規表現 一般化非決定性有限オートマトン(GNFA)

GNFAと正規表現の同値性 決定性有限オートマトン(DFA) 非決定性有限オートマトン(NFA) 正規表現 一般化非決定性有限オートマトン(GNFA)

正規表現の性質

正規表現の性質 有限な言語は正規言語 w1 | w2 | ⋯ | wn Σ* L w1 w2 ⋯ wn ⋯

正規表現の性質 r1, r2 が正規表現ならば Σ* L(r1) ∪ L(r2) は正規表現で表せる L(r1) L(r2) r1 | r2 ⋯

正規表現の性質 r1, r2 が正規表現ならば Σ* L(r1) ∩ L(r2) は正規表現で表せる L(r1) L(r2) r ⋯

正規表現の性質 a が偶数個ある文字列を 受理するDFA b p1 a a p2 b

正規表現の性質 a b が奇数個ある文字列を q2 受理するDFA b b q1 a

正規表現の性質 a a が偶数個あり b が奇数個ある文字列を 受理するDFAを構築する q2 b b q1 a b p1 a a p2 b

正規表現の性質 a それぞれの状態の直積を 状態とする q2 b (p1, q2) (p2, q2) (p1, q1) (p2, q1) b q1 a b p1 a a p2 b

正規表現の性質 a 開始状態同士のペアを 開始状態とする q2 b (p1, q2) (p2, q2) (p1, q1) (p2, q1) b q1 a b p1 a a p2 b

正規表現の性質 a 受理状態同士のペアを 受理状態とする q2 b (p1, q2) (p2, q2) (p1, q1) (p2, q1) b q1 a b p1 a a p2 b

正規表現の性質 a 両方の状態遷移を 満たすペアへ状態遷移を 作る q2 b (p1, q2) b q1 (p1, q1) a b p1 (p2, q2) a a a (p2, q1) p2 b

正規表現の性質 a が偶数個あり b が奇数個ある文字列を 受理するDFA (p1, q2) b b (p1, q1) a a a a (p2, q2) b b (p2, q1)

正規表現の性質 r が正規表現ならば L(r) は正規表現で表せる Σ* L(r) r (DFAの受理状態と非受理状態を 入れ替えれば良い) F

正規表現の性質 反復補題(ポンピング補題) L が正規言語ならば L によって定まるある数 m が存在し L に属する長さ m 以上の文字列は以下を満たすような xyz と表わせる ・ xy の長さは m 以下 ・ y の長さは1以上 i ・全ての i ≥ 0 について xy z はLに属する

正規表現の性質 反復補題の視覚的な説明 正規言語をDFAで表現したときのDFAの個数を m とし その言語に属する長さ m 以上の文字列が DFAで辿る状態遷移を一列に並べる q0 a1 q1 a2 q2 a3 ⋯ am qm am+1 ⋯ an qn

正規表現の性質 m 文字まで遷移した時点で状態は m + 1 個ある そのため、この中に必ず同じ状態がある q0 a1 q1 a2 q2 a3 ⋯ am qm am+1 ⋯ an qn

正規表現の性質 q0 a1 q1 a2 q2 a3 ⋯ am qm am+1 ⋯ an qn

正規表現の性質 同じ状態を重ねて書き直す q0 a1 q1 a2 q2 a3 ⋯ am qm am+1 ⋯ an qn ⋯ q0 ⋯ qi ⋯ qm am+1 ⋯ an qn

正規表現の性質 xyz と書ける i また xy z という文字列も受理状態に至ることがわかる xy で m 文字以下 y q0 x qi z qn

正規表現の性質 n n L = {a b | n ∈ ℕ} が正規言語だと仮定する するとDFAで表現できるのでその状態数を m とする m m 文字列 a b は反復補題より xyz と書けて y は a だけからなる文字列 i すると xy z も L に含まれるはずだがこれは矛盾 y=a q0 x qi k z qn

正規表現の性質 Myhill-Nerodeの定理 ある言語 L が与えられた時、文字列に対して同値関係を x ≈L y ⟺ ∀z ∈ Σ * [xz ∈ L ⟺ yz ∈ L] と定義すると以下は同値である ・ L が正規言語である ・ Σ * / ≈L の要素の数が有限個

正規表現の性質 C1, C2, C3, ⋯ は 同値関係 x ≈L y による同値類 有限個ならば L は正規言語 無限個ならば L は正規言語でない C1 Σ* C2 C3 ⋯ Myhill-Nerodeの定理の 視覚的な説明

プログラミングにおける 正規表現との違い

プログラミングにおける正規表現との違い https://developer.apple.com/documentation/foundation/nsregularexpression

• https://developer.apple.com/documentation/foundation/nsregularexpression

プログラミングにおける正規表現との違い プログラムで使用する記号 ・任意の1文字 ・オプション ・１回以上の繰り返し ・n回以上の繰り返し ・n回以上m回以下の繰り返し ・文字クラス … . r? r+ r{n,} r{n,m} [a-z] 対応する正規表現 a|b|⋯ ε|r rr * n r r* n n+1 m r |r |⋯|r a|b|⋯|z

プログラミングにおける正規表現との違い 後方参照は純粋な正規表現ではない <([a-zA-Z][a-zA-Z0-9]*)\b[^>]*>.*?</\1> 1番目のキャプチャグループ(括弧で囲まれた箇所)に マッチした文字列と同じ文字列にマッチする

プログラミングにおける正規表現との違い 再帰は純粋な正規表現ではない \((?>[^()]|(?R))*\) 正規表現全体にマッチする

参考文献 ・丸岡章 (2005) 計算理論とオートマトン言語理論 ーコンピュータの原理を明かすー サイエンス社 ・新屋良磨、鈴木勇介、高田謙 正規表現技術入門 技術評論社 (2015) 最新エンジン実装と理論的背景