正規表現のオートマトンへの変換osakasandaiac.jp.ppt

《正規表現のオートマトンへの変換osakasandaiac.jp.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、正規表現のオートマトンへの変換NFAとDFA機械的に変換正規表現のオートマトンへの変換入力1有限オートマトン決定性(DFA)非決定性有限オートマトン(NFA)入力2パターンマッチ正規表現テキストパターンマッチ非決定性有限オートマトン:入力に対する遷移先が複数存在する.決定性有限オートマトン:入力に対する遷移先が1つに定まる.正規表現を機械的に変換するにはNFAを介する方が容易1.正規表現からNFAへ正規表現の機械的な変換を補助するε遷移入力を読み込まずに無条件に別の状態へ移る遷移.DFAにはない.1423a5aεεa入力1→2→3遷移1→4→5遷移1.正規表現からNFAへ(

2、1)空文字列のNFA変換ε1.正規表現からNFAへ(2)1文字cのNFA変換c1.正規表現からNFAへ(3)正規表現XYのNFA変換Xは終了状態がのNFAに,Yは初期状態がのNFAに変換されているものとする.正規表現X正規表現YXのNFAYのNFAXYのNFA1.正規表現からNFAへ(4)正規表現X

3、YのNFA変換正規表現X正規表現YXのNFAYのNFA1εεεεX

4、YのNFA1.正規表現からNFAへ(5)正規表現X*のNFA変換正規表現X231XのNFA4εεX*のNFAεXが出現しない1→2→41.正規表現からNFAへ(5)正規表現X*のNFA変換X2314εεX*のNF

5、AεXが出現しないXが1回出現1→2→41→2→3→2→41.正規表現からNFAへ9εεεa(a

6、b)*aのNFA0a1εεabaab

7、()a*εε2345678a2.NFAからDFAへ・・・によるsubsetconstructionひとつの状態から遷移先が複数存在する.NFA状態集合DFAの新たな「状態」1aa3232NFA部分集合構成法2.NFAからDFAへ・・・部分集合構成法によるsubsetconstructionひとつの状態から遷移先が複数存在する.NFA状態集合DFAの新たな「状態」1aa32{2,3}321aNFADFA状態集合DFAの新たな「状態」2.NFAか

8、らDFAへ・・・部分集合構成法によるsubsetconstruction0ab1aa(a

9、b)*aのNFA2NFAの初期状態と,初期状態からε遷移によって遷移し得る状態を集めて状態集合を作り,これをDFA初期状態とする.{0}aε遷移なし2.NFAからDFAへ・・・部分集合構成法によるsubsetconstruction0ab1aa(a

10、b)*aのNFA2DFAの状態{0}に含まれるNFAの各「状態」から遷移し得る「(NFAの)状態」を集めて状態集合を作り,新たなDFAの「状態」とする.{0}aここには0しか状態はない0から遷移し得る状態は1だけ{1}aε遷移なし追加される状

11、態はない2.NFAからDFAへ・・・部分集合構成法によるsubsetconstruction0ab1aa(a

12、b)*aのNFA2DFAの状態{1}に含まれるNFAの各「状態」から遷移し得る「(NFAの)状態」を集めて状態集合を作り,新たなDFAの「状態」とする.{0}a{1}a1からbで遷移し得る状態は1だけb2.NFAからDFAへ・・・部分集合構成法によるsubsetconstruction0ab1aa(a

13、b)*aのNFA2DFAの状態{1}に含まれるNFAの各「状態」から遷移し得る「(NFAの)状態」を集めて状態集合を作り,新たなDFAの「状態」とする.{0}a{1}a

14、b{2}a2.NFAからDFAへ・・・部分集合構成法によるsubsetconstruction0ab1aa(a

15、b)*aのNFA2DFAの状態{1}に含まれるNFAの各「状態」から遷移し得る「(NFAの)状態」を集めて状態集合を作り,新たなDFAの「状態」とする.{0}a{1}ab{2}a{1,2}ε遷移なしε遷移なし追加される状態はない2.NFAからDFAへ・・・部分集合構成法によるsubsetconstruction0ab1aa(a

16、b)*aのNFA2DFAの状態{1,2}に含まれるNFAの各「状態」から遷移し得る「(NFAの)状態」を集めて状態集合を作り,新たなDFAの

17、「状態」とする.{0}a{1}aba{1,2}a2.NFAからDFAへ・・・部分集合構成法によるsubsetconstruction0ab1aa(a

18、b)*aのNFA2DFAの状態{1,2}に含まれるNFAの各「状態」から遷移し得る「(NFAの)状態」を集めて状態集合を作り,新たなDFAの「状態」とする.{0}a{1}aba{1,2}ab遷移先なし2.NFAからDFAへ・・・部分集合構成法によるsubsetconstruction0ab1aa(a

19、b)*aのNFA2DFAの状態{1,2}に含まれるNFA