0

有限オートマトンから正規表現を作成しようとしていますが、自分自身がこれに完全に固執していることに気づきました。使用する正規表現は次のようになります。

？=0または1
*=0以上
+=1以上
| =または
_=空の文字列
@=空のセット
（）=括弧

私が理解しているように、文字列は「b*」で終わる「a*」または「a+ bb +」で終わる必要があります。
私が今持っているのは((b*(a+(bb))*)*) 、「a」で終わる文字列を考慮していません。

言ったように、私はこれに100％立ち往生していて、これをどのように扱うべきかについて頭を悩ませることはできません。

画像： http： //img593.imageshack.us/img593/2563/28438387.jpg

コード：
オートマトン
FA のタイプ

状態
q1q2q3
q4
_
_

アルファベット ab
_

初期状態
q3

最終 状態
q3q4

遷移
q1aq2
q1 b q3
q2 a q2
q2 b q2
q3 a q4
q3 b q3
q4 a q4
q4 b q1

解決策やヒントをいただければ幸いです。

4

2 に答える 2

2

これをオートマトン用のツール ( Vcsn など) に渡すと、次のようになります。

In [1]: import vcsn

In [2]: %%automaton a
   ...: $  -> q3
   ...: q1 -> q2 a
   ...: q1 -> q3 b
   ...: q2 -> q2 a
   ...: q2 -> q2 b
   ...: q3 -> q4 a
   ...: q3 -> q3 b
   ...: q4 -> q4 a
   ...: q4 -> q1 b
   ...: q3 -> $
   ...: q4 -> $
   ...: 
mutable_automaton<letterset<char_letters(ab)>, b>

In [3]: a.expression()
Out[3]: (b+aa*bb)*(\e+aa*)

where\eは空の文字列を示します。それなら、構文変換の問題だけです。

グラフィカルに:

Vcsn グラフィカル レンダリング

この例をライブで見て、いじってみてください。

于 2015-05-22T07:38:54.077 に答える
0

q2 から最終状態に到達することはできません。これを削除すると、結果の DFA が変換しやすくなります。

私が理解しているように、文字列は「a*」で終わる「b*」か「a+bb+」で終わる必要があります。私が今持っているのは ((b*(a+(bb)) )です。 「a」で終わる文字列を考慮してください。

q3 が最終状態ではなく、q4 が初期状態であるとします。その場合、正規表現はどのようになりますか? それをあなたが望むものに変更するのはそれほど難しいことではありません.正規表現の複数の部分で同じ状態や遷移が記述されることを恐れないでください.

?もう 1 つのヒント: いずれかまたは|少なくとも 1 回は使用する必要があると確信しています。

于 2010-12-20T16:04:56.873 に答える