正規表現

1番と2番は簡略化されてますがどちらも他と同様language、つまり集合であることに注意します。（正確には、例えば正規表現 $R=a$ に対して言語 $L(R)=\{a\}$ とするようです）

また、 $\epsilon$ は「空文字列」という一つの文字列を含むlanguageであるのに対して、 $\emptyset$ は何の文字列も含まないlanguageということです。前回出てきたunionとconcatenationを使えば、

$R\cup\emptyset =R.\\ R\circ\epsilon = R.$

となるようです。 $\emptyset$ (empty set)は「何の文字列も受理しない」ということなので、分岐したところで何も効果はなし、対して $\epsilon$ (empty string)は「空文字列のみを受理する」ので、既存の正規表現に後続させても何も効果がない、、まあ、初めはこれくらいの砕けた言葉で理解しても良いでしょう。例えばこれを逆にすると、前者はRのみならずεも受け入れてしまうことになってしまいますし、後者だとRも含めて何も受理しなくなってしまうって感じですかね¹

また、

$R^{+}=RR^{*}$

で、正規表現における「0文字以上」のと「1文字以上」の+を数学的に表現できるようです。空文字列 $\epsilon$ を使えば、[tex: R^{+}\cup\epsilon =R^{}]という関係になりますね。

基本的にプログラミング言語における正規表現を知っていれば大丈夫っぽいですが、empty setと*の細かい扱いにはちょっと注意ですね。

正規表現と有限オートマトンの表現力は同等

「regularである」は「それを認識する有限オートマトンが存在する」です。こういうのは何回も書かないと慣れないですね。。

まず正規表現→regularの方ですが、こちらは先ほど述べた正規表現の6つの定義それぞれから、それらを認識するNFAを構築すれば良いことになります。正規表現 $R$ に対して、言語 $L(R)$ を認識するNFA $N$ を形式的に構成します。

といっても、4,5,6は以前構築した3つのNFAをそのまま適用するだけなので、ここでは割愛です。

GNFA; Generalized nondeterministic finite automata

regular→正規表現はこれよりちょっと大変でした。まず、NFAと正規表現の間に挟む、GNFAというオートマトンが導入されます。

DFA, NFAと比較すると、やっぱり $\delta$ が拡張されています。また、 $q_{accept}$ が集合ではなくone stateになっていることもポイントです。

$\delta$ の引数・戻り値の型から、[tex:(q{accept},q{start})]の組合せを除く全てのstate有向ペア（自己投射を含む）に1つずつ正規表現ラベルが割り当てられていることが分かりますね。²

正確にはこの3条件はGNFAの「特殊形」ということですが、まあすんなり理解できる感じの特徴ではあります。

証明は、一旦任意のDFAをGNFAに変換した上で、このGNFA特殊形の性質を使って正規表現へ変換していくという形をとるようです。

DFA to GNFA in the special form

始状態、終状態を新たに作って、矢が複数あったら1本にまとめる、1本もないところは $\emptyset$ ラベルで付け足す。この4操作でGNFAに変換できます。簡単ですね。

CONVERT(G)

続いて、正規表現への変換関数CONVERTを用意します。

CONVERT( $G$ ):

Let $k$ be the number of states of $G$ .
If $k=2$ , return the expression $R$ with which the single arrow connecting a start and accept state is labeled.
If $k>2$ , return CONVERT( $G^{'}$ ) where we construct GNFA $G^{'}=(Q^{'},\Sigma,\delta^{'},q _ {start},q _ {accept})$ by selecting any state $q_{rip}$ except for $q _ {start},q _ {accept}$ and letting

$Q^{'}=Q-\{q_{rip}\}\\ \delta^{'}(q_i,q_j)=(\delta (q_i,q_{rip}))(\delta (q_{rip},q_{rip}))^{*}(\delta (q_{rip},q_j))\cup (\delta (q_i,q_j))\text{ for any }q_i\in Q^{'}-\{q_{accept}\},q_j\in Q^{'}-\{q_{start}\}$