[数学]
正規表現の括弧とポンプの補題
emacs-jpのSlackコミュニティで見つけた話
問題
- 一般に、対応するカッコにマッチするような正規表現は書けない
- 「対応してるかはわからないけど決まった個数の開きカッコと閉じカッコがある」までしか調べられない
ちょっと考えてみる
((()))
これそもそも左端の括弧に対応する右端の括弧を取得する正規表現すら書くの難しくないか？
ポンプの補題（正規言語の反復補題）
正規言語が有限の場合、つまりその正規言語に含まれる文字列の長さに上限がある場合、 pをその正規言語に含まれる最大の文字列長より大きいと仮定すると、反復補題の形式的表現の論理式は常に真となる。
つまり反復補題が意味するところは、正規言語は有限か、無限であれば、任意の文字列の中間に表れる文字列に対する反復（任意回数の繰り返し）を、その正規言語が許容するということであり、いずれの場合でもないものは、正規言語ではないということである。
つまりポンプの補題を満たせば正規言語だし、そうでなければ正規言語ではない