正規表現をdfsaに変換する

私は正規表現をdfsaに変換するプロセスを研究しています。正規表現a | bc * d を満たしてdfsaを作成しました。

しかしhttp://hackingoff.com/compilers/regular-expression-to-nfa-dfa

ここでは以下のような正規表現を変換します。

そこには違いがありますか？私のdfsaは間違っていますか？

出典

2016-05-02 Youngin Na

bに一致した後に、正規表現エンジンは、右後c*が空の文字列（cがbとd間欠落することができる）を一致させることができるようにdを一致させることができるので、確かにあなたは間違いを含んでいます。

数値限定子は、以前のサブパターン（グループ、文字クラス、リテラル文字）が一致するものが0回以上一致します。

a|bc*d 
0| || | 
1 || | 
    || | 
    2| | 
    3 | 
     4

出典

2016-05-02 08:14:26

私は3に行かずに2から4へ行くオプションがあると思いますか？それは間違っていますか？ – AbhiNickz

これは、正確には、「b」から「d」（2から4まで）の「直接ルート」がある理由です。 'c *'は完全にオプションです。 –

でも、私はCが逃すことができるのをキャッチします。つまり、あなたが国家2にいれば、fsaは単に "c"を読まずにただちにdに行くことができます。私が正しいと理解しても、生成文字列は同じだとは思うけど、正規表現 "bc * d"は完全に解釈されるべきです。だから、私のdfsaでは、dを読んでいなくても、dの後にbを通り抜けることは可能です。私は正しいのですか？ –

正規表現をdfsaに変換する

答えて

関連する問題