アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

92

3

章 最も単純なコンピュータ

=> true

>>

pattern.matches?('ab')

=> true

>>

pattern.matches?('aba')

=> true

>>

pattern.matches?('abab')

=> true

>>

pattern.matches?('abaab')

=> true

>>

pattern.matches?('abba')

=> false

これは期待通りの結果です。パターンの構文から始めて、任意のパターンをNFA に変換する方法を

示すことで、構文に意味論を与えました。NFAは抽象機械の一種であり、私たちはすでにその実行方

法を知っています。これをパーサと組み合わせることで、正規表現を読んで特定の文字列にマッチす

るかどうか判断する、現実的な手段を得ることができます。この変換には、自由移動が活躍していま

す。自由移動のおかげで、それぞれのコンポーネントの振る舞いに影響を及ぼすことなく、小さな機械

をつなげて大きな機械にすることができました。

現実世界における正規表現の実装のほとんどは、文字通りパターンを有限オートマトンにコ

ンパイルして、その実行をシミュレートしているわけではありません。

Ruby

で使われている

Onigmo

ライブラリも同様です。ここで説明したやり方は、文字列に対する正規表現マッチン

グの高速で効率の良い方法ですが、グループ化や先読み／後読みといった、さらに進んだ機

能をサポートするのが難しくなります。そのため、たいていのライブラリは有限オ ...