Regular Expression(正規表現) Part17 (300ﾚｽ)
Regular Expression(正規表現) Part17 http://mevius.5ch.net/test/read.cgi/tech/1702684760/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
292: デフォルトの名無しさん [sage] 2025/11/20(木) 00:34:25.20 ID:mbRrNt6G DragonBook (第2版) の第3章まで読んだら、>>280 に書いた ε-遷移についての最初の疑問も氷解してしまったので、 一応伏線回収しておきます 「正規表現技術入門」では、ε-遷移を除去した後で部分集合構成法を行う、という流れで記述されていたので、 部分集合構成法を行うには前もって ε-遷移を除去しなければならない、と思い込んでいたのだけど、 その必要は全くなかったのでした 部分集合構成法の処理の中で一つ部分集合が得られたら、その集合の ε-閉包を取って (その集合に そこから ε-遷移する状態を全て加えて)、それを DFA の 1 状態とすればよいだけなのでした >>283 に書いた AI の回答が何となく歯切れが悪かった理由もこれで納得出来たわけで、 何でこんな簡単なことを思い付かなかったのか、我ながらアホでしたね 「正規表現技術入門」は章ごとに執筆者が違っていて、VM 型エンジンの章は鬼雲の作者が直々に書いていて説得力があるのですが、 DFA 型エンジンの章、とくにこの ε-遷移あたりの記述は今一つな感じです (エラそうに言ってますが) -- ところで DragonBook 3.9 節の「正規表現から直接 DFA を導くやり方」も読みました シンプソン構成法を経由せず、構文木から DFA を導くのはスゲーと思ったのですが followpos() の張るダイアグラムは一種の NFA 的なものなので、それを DFA に変換する時には やはり部分集合構成法と同じ手法を使うわけですね とは言え ε-遷移が存在しないので扱う状態数もずっと少なくて済むはずなので、 これを使って On-the-Fly 法を実装して行きたいと思ってます 何にせよ、DragonBook を読めと言ってくれた >>285 さんには感謝しかないです ありがとうございました http://mevius.5ch.net/test/read.cgi/tech/1702684760/292
300: デフォルトの名無しさん [sage] 2025/11/20(木) 23:34:16.70 ID:mbRrNt6G >>292 シンプソン構成法じゃなくてトンプソン構成法でした。すまそん 尊敬する Ken Thompson の名前を間違えるとはヤバ過ぎ http://mevius.5ch.net/test/read.cgi/tech/1702684760/300
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.597s*