前回の復習

列$x$の長さを$|x|$と書く. 普通に受け取ってしまったけど, そう言えばなんで絶対値記号を使うんでしょうね, absとlengthに同じ記号を使うのはおかしいのでは?

スター演算$a^*$ってプログラミング言語で言う正規表現の何に値するんだ? と思ったけど, よく考えたらそのまま*ですね.

言語$L$が正規表現で表現されるなら, $L$を識別するε入力付非決定性有限オートマトンが存在する.

どのような正規表現であっても, 元々の記号から

• 連接
• 和集合
• スター演算

いずれかを複数回使って表現されている.

つまり

data Regex = RegexSymbol String | RegexConjunction [Regex] | RegexUnion [Regex] | RegexStar Regex

ということですね.

資料のオートマトンの図が冗長に思えたので質問してみたら本当に冗長でした.

grepの名前の由来が｢get regular expression｣という話が出てきたのでググったら, edのg/re/pコマンドが元ネタになっていて, 後から複数の意味づけがされているらしいですね.

有限オートマトンで識別できない言語

例えば括弧の対応は有限オートマトン/正規表現では識別することが出来ない, 開き括弧の数を記憶する必要があるが, 有限オートマトンでは有限個しか記憶できないので, 不可能.

言語$\{a^n b^n | n >= 0\}$がある有限オートマトン$M$で識別できたと仮定する. この$M$の状態数を$m$とする. $M$の初期状態から記号$0$による遷移を$n$回$(n > m)$辿ったとする. このとき$n$回の遷移の状態が全て異なることは不可能である, よってこの遷移中には少なくとも2個の同じ状態が現れているはずである. この同じ状態が$r$回目と$k$回目に起きたとする. $(r ≠ k, n > r, n > k)$ ここで, 列$a^r b^r$は言語に属しているので, 受理されなくてはならない. しかし, $r$回目と$k$回目の遷移で同じ状態にいるはずなので, 列$a^r$と列$a^k$を読み込んだ時点で同じ状態にいるはずである. すなわち列$a^k b^r$も受理されることを意味する. これは$M$が言語$\{a^n b^n | n >= 0\}$を識別できないことを意味する.

正規表現で表現できる言語を正規言語という. 正規言語は有限オートマトンで表現できるクラスと等しい. 言語$\{a^n b^n | n >= 0\}$は正規言語ではない.

図に対する疑問

プレゼンに出された図で連接$R_1 R_2$の有限オートマトンが$○→^{R_1}○→^ε○→^{R_2}○$と書かれていて謎. 途中のイプシロンは要らないと思って質問してみたけれど, 講師の方も ｢要らない, なんでこう書かれているかはわからない｣ とのこと. 要る場合があるんでしょうか? 謎です.