正規表現＝正規言語？
ふとしたツイートがきっかけで正規表現について調べてた。
問．先頭文字が任意の文字aで、その後にaがn回続く文字列とマッチする正規表現は作れるか。
実は、２つ解があって、正規表現をどちらの意味に取るかによって異なる。
A1. できない。(正確には、アルファベットの数が有限なら、一応できる。が、ものすごく冗長になる。)
正規表現を「正規言語と等価な正規表現」として解釈した場合。
A2. できる。(下記はJavaの例)
"aaaa".matches("(.)\\1{n}"); // n=3ならtrue, それ以外ならfalse.
普段使う場合は２の意味で捉えてる人が多そうなんだけど、自分の場合は１の意味ありきで、あくまで２はその拡張と思ってたから、普通に「正規表現」という場合には出来ないものと思ってた。
となりのひとからの指摘で、両者が明確に異なるものであって、一般的には２を指すものと言われた。
気になって調べてみるとWikipediaさん曰く、
もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。
その後正規表現はテキストエディタ、ワードプロセッサをはじめとするアプリケーションソフトでパターンマッチ文字列を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。
だ、そうで。
「正規表現」という言葉自体が文脈依存となってあいまいなんだが、実用的な観点から２の解釈をすべきなのかなぁ。
