問題タブ [dfa]

明らかな選択は、すべての可能な入力を使い果たすことです。私はやったと思います。しかし、それが有効かどうかはよくわかりません。また、非決定性有限オートマトンの規則に違反していません。

私のNFAは次のように与えられます：(ab u aab u aba)*そして以下は私の図です。

私は何かを逃したことがありますか？

本を読んでいる間、私はこの疑問を抱きました。

それはそれについて言及しています

L = {s∈（0 + 1）* | n0（s）mod 7 = n1（s）mod5 = 0}は通常ですここで、n0（s）= sの0の数、n1（s）=sの1の数

さらにそれはそれを述べています

L = {s∈（0 + 1）* | d（s）mod 5 = 2およびd（s）mod 7！= 4}は規則的ではありません（文脈自由ではありませんが、再帰的です）。ここで、d（s）= sの10進値（例：d（101）= 5）

なんでそうなの？DFAにsの10進値を格納（記憶）するためのメモリがないためですか？しかし、その場合、どうして第一言語が規則的になるのでしょうか？

2 つの正規表現があります (簡単な例: "[0-9]+" と "[0123456789]+")。それらがまったく同じ入力に一致するかどうかを確認したいと思います。Javaでこのチェックを行うための組み込み関数はありますか? そうでない場合、チェックを行うための比較的簡単なアルゴリズムはありますか? ありがとう！

特定の正規表現の実装がDFAまたはNFAに基づいているかどうかという問題に直面しています。

これを理解するための出発点は何ですか。次のように尋ねることもできます。何を探していますか? 基本的なパターンおよび/または特性は何ですか? 適切で説明的なリンクまたは少しの比較 (正規表現に直接専念していなくても) はまったく問題ありません。

私は自分のテストでこの質問を間違え、誰かがそれを説明できるかどうか疑問に思っていました。そして、結論に達するためにとられたステップを示しました。どんな助けでもいただければ幸いです。

L_neq = {0 ^ i1 ^j|のPL証明で i <j} m状態のDFAが与えられた場合、誰かが文字列0 ^（m / 2）1 ^（m / 2 + 1）を選択します。次に、y = 0を選択し、ポンピングすることで、L_neqの外側にある文字列0 ^（m / 2 + 1）1 ^（m / 2 + 1）に到達できることを示します。この証明は正しいですか？なぜまたはなぜそうではないのですか？

さらに、この証明が間違っている場合は、正しい証明を書き留めてください。

ありがとう

右から5番目の記号として「1」を持つ文字列を受け入れるためにDFAで必要な状態の最小数はいくつですか。文字列はアルファベット{0,1}の上に定義されます。

私はしばらくこれに苦労していて、何も思い付くことができません。どんなポインタでも本当にありがたいです。

問題は、偶数の長さの単語のみを受け取るすべてのDFAの言語を前提として、それがPであるかどうかを証明することです。

開始状態から受け入れ状態までのすべてのパスを見つけるために、BFS /ダイクストラのアルゴリズムのようなもので特定のDFAを調べるチューリングマシンを作成することを検討しましたが、ループを処理する方法がわかりませんか？

ありがとう！

パーサーを使用せずにCSVファイルから行を引き離そうとしていますが、必要なのはphpを使用してコンマに基づいて文字列を分割することだけです。入力にコンマがない場合、これ自体はかなり簡単ですが、そうではありません。二重引用符で囲まれているコンマは無視したい。

最後の文を完全に無視して、問題自体を次のように変更することにしました。

二重引用符がない、または二重引用符のペアが散在しているコンマに基づいて文字列を分割したいと思います。

例：

ここで、*は一致し、xは一致しません。

これは正規表現の能力を超えていますか？そうでない場合、この種の入力を処理できる正規表現はありますか？

私は次のことを考えてきましたが、答えは肯定的だと思います。

通常のDFA許容言語のすべてのサブセットもDFA許容であるというのは本当ですか？

私はグーグルを検索しましたが、多くのページで、最小化されたDFAのデッド状態またはトラップ状態が削除されていることが示されています。私の質問は、トランジションが定義されていない場合、どうすればDFAのままでいられるかということです。それで、あなたは人々を何と言いますか？