正規表現（理論） とは？

形式言語理論における正規言語を記述するための数学的表記法。有限オートマトンと等価な表現力を持ち、文字列パターンの定義や解析の理論的基盤となっている。

ひよこ

プログラミングで使う正規表現と「理論の正規表現」って違うの？

ペンギン先生

理論では、文字や空文字列などを基本に、連結・選択・繰り返しで組み立てるよ。実装によっては後方参照や再帰などの拡張があるので、使える機能や表現力を区別する必要があるんだ

ひよこ

3つの演算だけで何ができるの？

ペンギン先生

たとえばa(a|b)*bなら、aとbだけからなる文字列のうち、aで始まりbで終わるものを表せるよ。ab・aab・abbなどが入るんだ。縦棒は選択、*は0回以上の繰り返しを表すよ

ひよこ

有限オートマトンと等価ってどういう意味？

ペンギン先生

正規表現で表せる文字列の集合は、有限個の状態を持つオートマトンでも判定でき、逆も成り立つんだ。見た目が同じという意味ではなく、扱える言語のクラスが同じということだよ

ひよこ

括弧の対応は正規表現では無理なの？

ペンギン先生

入れ子の深さを無制限に認めるなら、理論上の正規表現では表せないよ。有限の状態だけでは、任意の深さの対応を覚えられないんだ。ただし深さを決めて制限した場合とは区別しようね

ひよこ

括弧を調べるにはどうするの？

ペンギン先生

任意の深さなら、スタックを使う方法や文脈自由文法に基づく解析が使えるよ。PCRE2のように再帰を備える実装でも扱えるけれど、それは理論上の正規表現だけの機能ではないんだ

まとめ：ざっくりこれだけ覚えればOK！

「正規表現（理論）」って出てきたら「有限オートマトンで判定できる文字列の集合を書く方法」と思えばだいたいOK！

誤り・わかりにくい説明を報告する