この有限オートマトンを構築するにはどうすればよいでしょうか?

Question

私は離散数学のテストの勉強をしているのですが、この練習問題を見つけましたが、理解できませんでした。

「文字列内の要素の合計が偶数であり、かつこの合計が 3 より大きい、アルファベット Sigma = {0,1,2} の言語用の基本的な有限オートマトン (DFA、NFA、NFA-lambda) を構築します。」

この正規表現に関連付けられた言語を連結するように、2 つの言語を連結するクリーンの定理を使用してみました。

(00 U 11 U 22 U 02 U 20)* - 偶数要素

これと

(22 U 1111 U 222 U 2222)* - 合計が 3 より大きいもの

これには意味がありますか??私の正規表現はたるんだと思います。

Answer 1

表記が少し曖昧なので、もしかしたら完全に誤解しているかもしれません。その場合、以下は無視してください。まだ到着していないようです:

• * は「0 回以上」を意味すると思います。ただし、合計が 3 以上の文字列が 1 つ出現する必要があります。+ (「1 回以上」) が必要だということです。
• 合計が 3 以上の文字列のリストに 112 と 211 がありません。
• このリストの 222 と 2222 は不要です。
• これらの文字列にはすべて、任意に 0 を散在させることができます。
• 00 の合計は 0 の合計と同じです。

---

編集： これはどう （ACC 唯一の受け入れ国である、 ドットソース):

オートマトン http://student.science.uva.nl/~sschroev/so/885411.png

州で ある そして c 文字列の合計は常に奇数になります。州で 始める, b そして ACC 和は常に偶数です。さらに、 始める 合計は 0 です。 b それは2であり、 d それは >= 4 です。これはかなり簡単に証明できます。したがって、受け入れ状態 ACC すべての基準を満たしています。

編集2: これは、要求された言語を受け入れる正規表現だと思います。

0*(2|(1(0|2)*1))(0*(2|(1(0|2)*1))+

Answer 2

これは、あなたの質問に答えるが、かどうかわからない：あなたは正規表現を提出する必要がありますか？またはFSMは何だろう？

いずれにせよ、最初のFSMを描くために役立つかもしれない、と私はをのこれが正しいDFAだと思います：

FSM http://img254.imageshack.us/img254/5324/fsm。 PNGする

その場合は、あなたの正規表現の構築時に

は、（覚えて、プログラミング「正規表現」とは異なる構文を持つ）：

「あなたが望むよう0何度でも」を示すために0*。あなたの文字列の0は、マシンの状態を変更しないので、これは理にかなっています。 （参照、FSMに、0だけ自体にループバック）

あなたは合計で少なくとも4に到達するまで、

-

あなたは、「112」や「22」などのさまざまな組み合わせを考慮して必要があると思います。

あなたの合計が3以上である、とさえ、その場合は（0 | 2）*最終状態であなたを続けるだろう。受理状態であなたを置くために*

|（2 0）そうでない場合（合計> 3、および奇数）あなたは1のようなものが必要だろう。

（このことができ、またはその右の場合はどうか知りません！ - しかし、それはスタートかもしれません）。

Answer 3

各式、ステファンによって案内されるようであってもよい。

（0 * U 2 * U 11）* - さえ合計

この1と

（22 U 11 U 222 U 112 U 211 U 121）+ - その和であるものよりも大きい3

オートマトンの設計に役立つだろう、よりsimplfiedすることができれば。

この私にはわかりません

Answer 4

私はそれが簡単だけの状態の観点で考えることを見つけます。使用する5つの状態：0、1、2、EVEN、ODD

トランジションます：

State, Input -> New State

(0, 0) -> 0
(0, 1) -> 1
(0, 2) -> 2

(1, 0) -> 1
(1, 1) -> 2
(1, 2) -> ODD

(2, 0) -> 2
(2, 1) -> ODD
(2, 2) -> EVEN

(ODD, 0) -> ODD
(ODD, 1) -> EVEN
(ODD, 2) -> ODD

(EVEN, 0) -> EVEN
(EVEN, 1) -> ODD
(EVEN, 2) -> EVEN

のみEVEN受理状態である。