Formal Language - Ch3 正則表達式 Regular Expression, RE

正則表達式簡介 (Regular Expression, RE)
正規表示式使用單個字串來描述、匹配一系列符合某個句法規則的字串。在很多文字編輯器裡，正則運算式通常被用來檢索、替換那些符合某個模式的文字。


正則表達式在代碼中常簡寫為regex、regexp或RE，許多程式設計語言都支援利用正則運算式進行字串操作。例如，在Perl中就內建了一個功能強大的正則運算式引擎。正則運算式這個概念最初是由Unix中的工具軟體(例如sed和grep)普及開的。



正則表達式定義
正規表示式可以用形式化語言理論的方式來表達。正規表示式由常量和運算元組成，它們分別指示字串的集合和在這些集合上的運算。給定有限字母表Σ，

• 定義了下列常量：空集、空串、文字字符
• 定義了下列運算：串接、聯集、Kleene星號 (詳見ch1, ch2 regular operations)

上述常量和運算元形成了克萊尼代數。為了避免括弧，假定Kleene星號有最高優先級，接著是串接，接著是聯集。例如，(ab)c可以寫為abc而a U (b(c*))可以寫為a U bc*。下面是一系列的例子 :

Regular Expression和finite automaton等價

Theorem : Every RE has an equivalent NFA

我們要證明RE和NFA等價，也就是任找一個RE我們都可以找到一個NFA使兩者recognize的language相同，反之亦然。

RE 轉 NFA : 改寫方式的舉例如下，跟ch2 regular operation證明使用的概念相同。

NFA 轉 RE : 改寫方式如下。

1. 先把原本的NFA轉成 generalized nondeterministic finite automaton (GNFA) : GNFA是開始跟結束都只有一個state的NFA。
2. 再逐漸化減state，當剩一開始自己造的start和accept state時，路徑上的表達式就是regular expression。

例題 : 有loop的NFA轉RE

把下圖的DFA用GNFA的方法轉成RE，先刪狀態0再刪狀態1。

Answer : 1*0(0*(11*0)*)*

Regular expression visualizer : 這個網站可以驗證妳的RE轉DFA有沒有寫對，很好用!

http://regexvisualizer.apphb.com/

Reference

交大陳穎平教授正規語言講義

wiki - 正規表示式
http://zh.wikipedia.org/wiki/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F