正規表現（理論）とは何ですか？

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

正規表現（理論）のポイントは？

正規言語は形式言語のチョムスキー階層で最も単純なクラス（Type-3）に属する。正規表現・有限オートマトン（DFA/NFA）・正規文法の3つは等価な表現力を持つ。プログラミングの正規表現（regex）は理論的な正規表現を拡張したもの

【せいきひょうげん（りろん）】

💡 文字列の世界を数学で記述する最初の一歩

📌 このページのポイント

正規表現（理論）のイメージ

ひよこ

ペンギン先生

もとは同じものだけど、プログラミングの正規表現は後方参照や先読みなど理論を超えた拡張が入っているんだ。理論上の正規表現は連結・選択・繰り返しの3つの演算だけで構成されるよ

ひよこ

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

ペンギン先生

たとえば「aで始まってbで終わる文字列」や「0と1が交互に並ぶ列」のようなパターンを定義できるよ。記号で書くと a(a|b)*b のようになるんだ

ひよこ

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

ペンギン先生

正規表現で書けるパターンは必ず有限オートマトン（状態遷移マシン）で判定でき、逆も成り立つということだよ。クリーネの定理として証明されているんだ

ひよこ

正規表現で表せないものもあるの？

ペンギン先生

あるよ。たとえば「括弧の対応が正しいかチェックする」は正規表現では不可能なんだ。入れ子の深さを覚える必要があるけど、有限オートマトンはメモリが有限だからね

ひよこ

じゃあ括弧のチェックにはもっと強い仕組みが必要なんだね！

ペンギン先生

そう、それにはチョムスキー階層で一段上の文脈自由文法とプッシュダウンオートマトンが必要になるよ。正規表現はType-3、文脈自由はType-2というように、言語の複雑さに応じて理論が階層化されているんだ

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

「正規表現（理論）」って出てきたら「文字列パターンを数学的に定義する仕組みで、有限オートマトンと同じ力を持つ形式言語の基礎理論」と思えればだいたいOK！

📖 おまけ：英語の意味

「Regular Expression (Theory)」＝正規表現（理論）

💬 Regular（規則的な）Expression（表現）で、数学者スティーブン・クリーネが1950年代に正規集合の表記法として考案したのが始まりだよ