正規表現のこと

正規表現とは、次のような規則によって作られる表現をさす。

• ε(空記号列)
• 任意のアルファベット*1
• RとSが正規表現ならばR*(ゼロ回以上の反復), RS(連結), R|S(RまたはS)は正規表現である(優先順位はこの順)
• 気が向いたら括弧を使ってもいい

正規表現が与えられたとき、それを認識する非決定性有限オートマトンを機械的に生成できる。また、そこから決定性有限オートマトンを作ることもできる。

このあたり、一度自分でやってみないとしっくりこないから、週末の間にやってみること(自分用メモ)。

*1:英語の、という意味ではなく、なんというか、もうすこし一般的な意味