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

6.5K Views

September 10, 22

スライド概要

iOSDC2022の発表資料
9/11(Sun) 14:10〜 Track D

profile-image

ヒキコモリプログラマー

シェア

埋め込む »CMSなどでJSが使えない場合

各ページのテキスト
1.

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

2.

自己紹介

3.

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

4.

用語

5.

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

6.

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

7.

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

8.

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

9.

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

10.

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

11.

導入

12.

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

13.

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

14.

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

15.

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

16.

🙅

17.

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

18.

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

19.

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

20.

正規表現の定義

21.

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

22.

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

23.

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

24.

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

25.

正規表現の定義 連接 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}

26.

正規表現の定義 繰り返し 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, ⋯}

27.

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

28.

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

29.

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

30.

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

31.

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

32.

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

33.

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

34.

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

35.

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

36.

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

37.

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

38.

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

39.

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

40.

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

41.

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

42.

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

43.

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

44.

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

45.

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

46.

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

47.

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

48.

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

49.

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

50.

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

51.

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

52.

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

53.

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

54.

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

55.

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

56.

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

57.

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

58.

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

59.

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

60.

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

61.

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

62.

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

63.

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

64.

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

65.

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

66.

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

67.

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

68.

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

69.

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

70.

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

71.

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

72.

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

73.

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

74.

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

75.

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

76.

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

77.

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

78.

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

79.

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

80.

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

81.

DFAとNFAの同値性

82.

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

83.

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

84.

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

85.

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

86.

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

87.

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

88.

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

89.

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

90.

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

91.

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

92.

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

93.

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

94.

正規表現とNFA

95.

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

96.

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

97.

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

98.

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

99.

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

100.

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

101.

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

102.

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

103.

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

104.

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

105.

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

106.

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

107.

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

108.

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

109.

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

110.

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

111.

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

112.

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

113.

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

114.

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

115.

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

116.

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

117.

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

118.

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

119.

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

120.

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

121.

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

122.

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

123.

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

124.

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

125.

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

126.

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

127.

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

128.

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

129.

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

130.

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

131.

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

132.

GNFAと正規表現の 同値性

133.

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

134.

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

135.

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

136.

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

137.

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

138.

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

139.

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

140.

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

141.

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

142.

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

143.

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

144.

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

145.

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

146.

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

147.

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

148.

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

149.

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

150.

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

151.

正規表現の性質

152.

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

153.

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

154.

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

155.

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

156.

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

157.

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

158.

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

159.

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

160.

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

161.

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

162.

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

163.

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

164.

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

165.

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

166.

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

167.

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

168.

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

169.

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

170.

正規表現の性質 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

171.

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

172.

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

173.

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

174.

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

175.

プログラミングにおける正規表現との違い プログラムで使用する記号 ・任意の1文字 ・オプション ・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

176.

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

177.

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

178.

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