# HG changeset patch # User Masataka Kohagura # Date 1431425208 -32400 # Node ID ef709768b9cf6bc78b7e2c2e714cd3eca93c416d # Parent 14d14dcb82195b818ab579efb2f060fdc08aaac7 add image diff -r 14d14dcb8219 -r ef709768b9cf 2015/0512.html --- a/2015/0512.html Mon May 11 15:54:07 2015 +0900 +++ b/2015/0512.html Tue May 12 19:06:48 2015 +0900 @@ -102,7 +102,7 @@

- Masataka Kohagura 5th, May , 2015 + Masataka Kohagura 12th, May , 2015

@@ -126,24 +126,6 @@

今日の話題

- 正規表現について -
- オートマトンについて -
- 正規表現の基本三演算 -
- 正規表現の他の演算 -

- -

正規表現について

@@ -151,10 +133,9 @@
文章からあるパターン文字列を検索したいときに使用する
- (e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed) -
- 正規表現は有限オートマトンで表現できる + (e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed)
+ . (ピリオド) : 改行コード以外の任意の1文字
+ * : 直前の文字の 0 回以上の繰返し

@@ -165,6 +146,21 @@

入力に対して内部の状況に応じた処理を行う結果を出力する仮想的な自動機械の概念

+ 正規表現はオートマトンで表現することができる。 +

+ 非決定性有限オートマトン NFA(Non-deterministic Finite Automaton)と、非決定性有限オートマトンDFA(Deterministic Finite Automaton)が存在する。 +

+ 非決定性有限オートマトン : 1つの入力に対して複数の遷移先が存在する +

+ 決定性有限オートマトン : 1つの入力に対して遷移先が1つだけ +

+ @@ -172,14 +168,17 @@

正規表現の基本三演算

- 正規表現は「連接」「選択」「繰返し」の演算が備えられている + 正規表現は「連接」「選択」「繰返し」の演算が備えられている
R,S という 2 つの正規表現が存在すると仮定する。
連接「RS」: R の直後に S が続くパターン
+
選択「R|S」: R もしくは S が出現するパターン
+
繰返し「R*S」: 「*」の直前(R)が 0 回以上出現するパターン
-
+
+
基本三演算は結合順位が存在する
@@ -202,7 +201,7 @@
- 「R{1,3}」: 「{}」の直前のパターンが 1 or 3 回出現するパターン
+ 「R{1,3}」: 「{}」の直前のパターンが 1 〜 3 回出現するパターン
@@ -213,6 +212,31 @@

実装について

+ まずは基本三演算を実装していく。 +

+ R*(T|S)U をオートマトンで表現してみる +

+ 状態と入力に対する遷移先、遷移したかどうかフラグで管理する。 +

+    
+typedef struct Automaton {
+    int state;
+    unsigned char input_char;
+    int next_state;
+    bool next_state;
+};
+    
+