オートマトン内のDFAの開始状態

Question

Σ= {0,1} *上のすべての文字列を受け入れ、同じ記号（例：-0110,10101など）で終わるDFAを設計する必要があるとします。許容される文字列ですか？つまり、開始状態は最終状態ですか？

Answer 1

はい。

文字列εは{0,1} *に属し、その開始および終了シンボルは、それが意味するものに完全に依存DFA

Answer 2

によって受け入れられるべきdifferent.Soれません。人間の言語はあいまいで不正確です。だからこそ正規表現のような形式主義を発明するのです。

これが練習問題であれば、私はあなたに明確化のためにエクササイズを行っている人を尋ねるでしょう。表面には、二つの解釈が妥当なようだ：

• 空の文字列は、そう、開始と同じ文字で終わらない
• それは除外すべきではないので、空の文字列は、起動して、異なる文字で終わっていませんそれは含まれてはならない

練習で、元の言葉遣いを持っている場合は、引用符を付けることができますが、答えは明らかではありません。宿題の場合は、それぞれの解釈に1つずつ、常に2つのDFAを用意して、あいまいさについて何らかの議論をすることができます。

あなたが作成した質問だけの場合は、あなたの言語で空の文字列を使用するかどうかを自分で答える必要があります。