このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

［参照用 記事］

要約版・明瞭正規表現

雑記／備忘

明瞭正規表現については、次の2つの記事で述べています。

Catyに正規表現型（regular expression type）を入れる際に必要となるのでメモしておいたわけですが、説明が完結してません。丁寧な説明を書く余裕がないので、手短な要約を作っておくことにします。上の2つの記事、それと次の入門的記事の内容は前提とします。

明瞭正規表現とは何か

Bruggemann-Klein & Wood の論文 One-Unambiguous Regular Languages (1997) では、one-unambiguousという言葉が使われています。直訳すると「1-非曖昧（イチヒアイマイ）」ですが、とってもいいにくいので、僕は明瞭（crisp）という形容詞を使うことにしました。

正規表現が明瞭とは、マクノートン／山田（McNaughton and Yamada）の方法*1で受理オートマトンを作ったとき、そのオートマトンからイプシロン遷移を除去するだけで決定性になることです。明瞭性（crispness）は、言語に関する性質ではなくて、正規表現に関する性質です。言語に対しても「明瞭な正規言語」という概念を定義できなくもないですが、実用上の意味は（たぶん）薄いでしょう。

正規表現の復習

Aをアルファベットとして、A* はAのクリーネ閉包*2、Pow(A*) はそのベキ集合とします。Pow(A*) の要素はアルファベットA上の言語なので、Lang(A) := Pow(A*) と置きます。

Lang(A)の部分集合Bを固定します。正規表現は、Bに対して相対的に定義されます。通常、B = { {a} | a∈A} のように、「長さ1の列だけからなる単元集合」の集合をBとして取るので、Bを明示することは少ないですね。しかし、Bを色々と変えたほうがいいこともあるので、ベースとなる言語の集合Bを意識したほうがいいと思います。Bは次の条件を満たすとします。

  1. L∈B ならば、Lは空ではない。
  2. L∈B ならば、Lは空列を含まない。
  3. L, M∈B、L≠M ならば、L∩M は空集合である。

さて、ベースB上の正規表現を考えましょう。Bの要素に対応する基本記号を準備すべきですが、メンドウなので、Bの要素とそれを表す記号を同一します。ベースB上の正規表現は、次のように帰納的に定義されます。

  1. Bの要素は正規表現である。
  2. 定数（記号） 0, 1 は正規表現である。
  3. E、F が正規表現のとき、(E, F) は正規表現である。
  4. E、F が正規表現のとき、(E | F) は正規表現である。
  5. Eが正規表現のとき、E+ は正規表現である。
  6. 以上に定義したものだけが正規表現である。

「この機会にマスターしようぜ、正規表現、構文図、オートマトン」と若干変えてあるところがあります。（変えた理由は、明瞭性の定義が少し簡潔になるからです。）

  1. 定数 0, 1 を導入しました。それぞれ、空集合と“空列からなる単元集合”を表す記号です。整数値の 0, 1 じゃありません。
  2. E+ をプライマリーな定義に採用しています。E? と E* は E+ から定義します： E? := (E | 1)、E* := (1 | E+) 。

明示的に言及してませんが、式のグルーピングのために括弧（'('と')'）を自由に使ってかまいません。また、括弧が付いてないときの演算子の優先順位は、強い順に '+'、','、'|' です。',' と '|' は二項演算として導入してますが、n項演算 (E1, ..., En)、(E1 | ... | En) を定義して使ってもかまいません。

正規表現の意味

B⊆Lang(A) に相対的に定義された正規表現の意味を定義します。正規表現Eの意味を《E》と記します。

  1. LがBの要素のとき、《L》 = L
  2. 《0》 = 空集合、《1》 = {ε} （εは空列）
  3. 《(E, F)》 = 《E》《F》
  4. 《(E | F)》 = 《E》∪《F》
  5. 《E+》 = 《E》∪(《E》《E》)∪ (《E》《E》《E》)∪ ...

3番の右辺は、言語の連接演算を意味します。5番に出てくる併置も言語の連接演算です。《E》《E》 = 《E》2 のように累乗を使ったほうが見やすいかもしれません。

正規表現の明瞭性

言語L（L∈Lang(A)）に対して、ε(L) は「正規表現とオートマトン：イプシロン指標」で述べたイプシロン指標とします。正規表現Eに対しても、ε(E) := ε(《E》) としてイプシロン指標を定義します。

言語Lに対して、First(L)は、Lの要素である列の“最初に出現するAの要素”の集合とします。

  • First(L) = {first(x) | x∈L}

正規表現Eに対しても、First(E) := First(《E》) としてFirstを定義します。

[追記]この後で出てくる正規表現の明瞭性の定義が間違ってました(苦笑)。2年ちょっと前にも同じような間違いをしでかして訂正していたり（http://d.hatena.ne.jp/m-hiyama-memo/20100609/1276065813）。訂正は取り消し線（del/ins）を使って行いますが、FollowLast集合の定義が必要なので、それを書き足します。[/追記]

言語Lに対して、Aの部分集合 FollowLast(L) を次のように定義します。

  • a∈FollowLast(L) ⇔ ∃u, v∈A*.[u∈L ∧ uav∈L]

終端できるLの列がさらに続くときに、“「続きの最初」に出現するAの要素”の集合が FollowLast(L) です。正規表現Eに対しても、FollowLast(E) := FollowLast(《E》) としてFollowLastを定義します。

便宜的な約束として、言語Lに対して、1L = L、0L = 空集合 とします。（今回は使わない。）

記号・記法の約束が済んだので、正規表現の帰納的定義に沿って正規表現Eの明瞭性を定義しましょう。

  1. LがBの要素のとき、Lは明瞭である。
  2. 0, 1 は明瞭である。
  3. (E, F) が明瞭とは、EもFも明瞭で、First(E)∩ε(E)First(F)FollowLast(E)∩First(F) が空集合のこと。
  4. (E | F) が明瞭とは、EもFも明瞭で、First(E)∩First(F) が空集合のこと。
  5. E+ が明瞭とは、Eが明瞭で、 First(E)∩FollowLast(E) が空集合であること。

正規表現をオートマトンにコンパイルするとき、Bの要素はトークンとして扱えて、等値性や所属性が一瞬で判断できると仮定します。また、オートマトンを作るときは、end-of-sequenceマーカーを使うことにします。

この仮定のもとで、上記の明瞭性の定義が冒頭に挙げた命題「マクノートン／山田の方法で作った受理オートマトンが、イプシロン遷移を除去すれば決定性である」と同値になることを示すのは練習問題とします。

なお、ツリー正規表現とツリーオートマトン*3に対しても明瞭性の概念は同様に定義できます。

*1:グラシュコフ（Glushkov）、ケン・トンプソン（Ken Thompson）といった人名が形容詞として出てくることもあります。ほぼ同時期に複数の人が似たアルゴリズムを発見したようです。A Taxonomy of Finite Automata Construction Algorithms とかに詳しいようです（って、僕はこの論説読んでないけど）。

*2:A* は連接によるモノイド構造を持つとします。つまり、A* をAから作られた自由モノイドと解釈します。

*3:ツリー正規表現とツリーオートマトンに関する纏まった説明って、僕、してなかったんですね。断片的なら「お絵描きで学ぶ・無限正規ツリーとBNF(バッカス／ナウア形式)」とか「ツリーパターン入門」とか。