Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
正規表現のはなし / regex theory
Search
USAMI Kosuke
October 15, 2022
Science
0
860
正規表現のはなし / regex theory
※ Docswell に移行しました
https://www.docswell.com/s/usami-k/Z389Q2-regex-theory
USAMI Kosuke
October 15, 2022
Tweet
Share
More Decks by USAMI Kosuke
See All by USAMI Kosuke
Onsager代数とその周辺 / Onsager algebra tsudoi
usamik26
0
640
Apple HIG 正式名称クイズ結果発表 / HIG Quiz Result
usamik26
0
190
ゆめみ大技林製作委員会の立ち上げの話 / daigirin project
usamik26
0
330
@ViewLoadingプロパティラッパの紹介と自前で実装する方法 / @ViewLoading property wrapper implementation
usamik26
0
480
これからUICollectionViewを実践活用する人のためのガイド / Guide to UICollectionView
usamik26
1
750
Xcodeとの最近の付き合い方のはなし / Approach To Xcode
usamik26
2
670
UICollectionView Compositional Layout
usamik26
0
800
Coding Swift with Visual Studio Code and Docker
usamik26
0
520
Swift Extension for Visual Studio Code
usamik26
2
1k
Other Decks in Science
See All in Science
SciPyDataJapan 2025
schwalbe10
0
240
機械学習 - DBSCAN
trycycle
PRO
0
940
アナログ計算機『計算尺』を愛でる Midosuji Tech #4/Analog Computing Device Slide Rule now and then
quiver
1
210
Symfony Console Facelift
chalasr
2
460
A Guide to Academic Writing Using Generative AI - A Workshop
ks91
PRO
0
120
オンプレミス環境にKubernetesを構築する
koukimiura
0
290
メール送信サーバの集約における透過型SMTP プロキシの定量評価 / Quantitative Evaluation of Transparent SMTP Proxy in Email Sending Server Aggregation
linyows
0
970
高校生就活へのDA導入の提案
shunyanoda
0
1.8k
04_石井クンツ昌子_お茶の水女子大学理事_副学長_D_I社会実現へ向けて.pdf
sip3ristex
0
530
機械学習 - K-means & 階層的クラスタリング
trycycle
PRO
0
1k
[Paper Introduction] From Bytes to Ideas:Language Modeling with Autoregressive U-Nets
haruumiomoto
0
110
Explanatory material
yuki1986
0
350
Featured
See All Featured
4 Signs Your Business is Dying
shpigford
184
22k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Making Projects Easy
brettharned
116
6.3k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
Building Adaptive Systems
keathley
43
2.7k
The Power of CSS Pseudo Elements
geoffreycrofte
77
5.9k
How to Think Like a Performance Engineer
csswizardry
25
1.8k
The Cost Of JavaScript in 2023
addyosmani
51
8.6k
Thoughts on Productivity
jonyablonski
69
4.7k
The World Runs on Bad Software
bkeepers
PRO
70
11k
Bootstrapping a Software Product
garrettdimon
PRO
307
110k
How GitHub (no longer) Works
holman
314
140k
Transcript
正規表現のはなし 宇佐見公輔 第25回日曜数学会(2022年10月15日)
自己紹介 宇佐見公輔(うさみこうすけ) 職業:プログラマ 趣味:数学 近況 第3回すうがく徒のつどい:講演(4月) iOSDC Japan 2022:登壇、技術記事執筆(6〜9月) 技術書典13:技術同人誌執筆(8〜9月)
正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 2
正規表現とは プログラミング言語で、文字列の検索(パターンマッチ)に使われる汎用的な文法。 テキストエディターなど各種ツールでの文字列検索機能でもよく使われる。 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 3
正規表現の記法 「 a 」は a にマッチ、「 b 」は b にマッチ
「 (a|b) 」は a または b にマッチ 「 [a-z] 」は a 〜 z のどれでもマッチ 「 . 」は任意の1文字にマッチ 「 a* 」は任意個の a からなる文字列にマッチ(空文字列、 a 、 aa 、、) 「 a+ 」は1個以上の a からなる文字列にマッチ( a 、 aa 、 aaa 、、) 「 (a|b)* 」は aaa 、 abab 、 baab 、 bbbbb 、などにマッチ 「 .* 」は任意個の文字からなる文字列にマッチ 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 4
正規表現の基本三演算 正規表現は次の3つの演算で生成される。 連接:正規表現 と に対して、それを並べた 選択:正規表現 と に対して、そのどちらかにマッチする 繰り返し:正規表現 に対して、その任意個の繰り返し
例: 「 a+ 」は「 aa* 」と書ける 「 [a-z] 」は「 (a|b|c|...|z) 」と書ける 「 . 」はすべての文字の選択で書ける(※文字集合は有限集合) 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 5
余談:正規表現という言葉 正規表現は「regular expression」の訳だが・・・。 「regular」 一般に「regular」は「正則」と訳されることが多そう そもそも「regular」という言葉が妥当かどうか? 「expression」 一般に「expression」は「式」と訳されることが多そう 「表現」と言われると「representation」を連想するかも? 正規表現のはなし
/ 宇佐見公輔 / 第25回日曜数学会 6
正規表現と集合 正規表現そのものを直接考える代わりに、集合で考える。 正規表現 にマッチする文字列の集合を の受理文字列集合と呼び、 と書く。 例: ある文字列が正規表現 にマッチするかという問題が、集合 の元かという問題
になる。 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 7
正規言語 文字列集合を定式化しておく(形式言語理論)。 :文字集合(有限集合とする) :文字列(= の元を有限個並べたもの)全体の集合 長さ の文字列を と書くことにする(空文字列) とする たとえば、
のとき の部分集合 を言語と呼ぶ 言語 がある正規表現 の受理文字列集合 と一致するとき、 を正規言語 と呼ぶ 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 8
正規言語の定式化 正規表現を使わずに正規言語を定義することができる。 空集合 は正規言語、空文字列のみの集合 は正規言語 について は正規言語 と が正規言語ならば、選択 は正規言語
と が正規言語ならば、連接 は正規言語 が正規言語ならば、Kleene閉包 は正規言語 これらの条件にあらわれない言語は正規言語ではない ※Kleene閉包 は、 の元を重複を許して有限個取り出して連接した文字列の全体 からなる集合。 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 9
正規言語の代数構造 選択の結合法則 選択の交換法則 選択の単位元 連接の結合法則 連接の単位元 零元 分配法則 、 正規表現のはなし
/ 宇佐見公輔 / 第25回日曜数学会 10
正規性の判定 上の言語 があるとき、 上の同値関係 を次で定義する。 Myhill-Nerodeの定理 上の言語 が正規言語であることと、商集合 が有限集合であることは 同値。
これを言語の正規性の判定に使うことができる。また、より条件が緩いポンピング補 題を正規性の判定に使うことができる。 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 11
より進んだ話題 有限オートマトン 正規表現マッチングの計算モデルとして、有限オートマトンがある 正規表現と決定性有限オートマトンは等価 正規性の利点 最適化問題が決定問題であり、そのアルゴリズムの方法論も確立されている 非正規な正規表現 プログラミングで使われている正規表現のうち後方参照や再帰の記法は、実 は正規ではない 形式言語理論
形式言語の理論は、正規表現以外にもさまざまな応用がある 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 12
参考文献 ※右端はiOSDC Japan 2022のセッション 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 13