問題タブ [automata-theory]

r と r の DFA が定義されている場合に、r* の DFA を見つけるメソッドの例を示してください。そして、どのように考えるのですか？教科書を読んだのですが、よくわかりません。ありがとうございました。

言語 L_n に文字セット Sigma = {a_1, ..., a_n} があるとします。L_n には、ある文字を奇数回含む単語が正確に含まれています。同様に、L_n^i が、各単語に奇数個の a_i が含まれる言語である場合、L_n = L_n^1 union ...union L_n^n となります。

L_n を受け入れる NFA と 2^n 状態の DFA も作成しました。

これがこの言語を受け入れる最小の DFA であることを証明する必要があります。L_n を受け入れる k < 2^n 状態の DFA があると仮定するためのヒントが与えられ、次にSigma^* にいくつかの文字列u、vがあることを示します。偶数回であり、DFA は両方で同じ状態で終了する必要があります。

長さ n のすべての文字列を考えてみてください。おそらく、文字a,bのみを使用して長さ n のすべての文字列を検討してください。k < 2^n の状態があるため、このような 2 つの文字列を同じ状態に送信する必要があります。このセットで拒否された文字列は、a と b の数が偶数の文字列ですが、これらの2 つのインスタンスが同じ状態になるかどうか、または同じ状態になった場合、それがどのように問題になるかを知る方法はありません。

おそらく、a_1 が 1 回または 0 回発生し、a_2 が 1 回または 0 回発生する文字列のすべての選択肢を検討してください。これらには 2^n の選択肢があるため、これらのいくつかの 2 つが同じ状態になる必要があります。ここの言語にない唯一の文字列は空の文字列です。それでも私は立ち往生しています。

言語を生成する文脈自由文法 H を与える

ヒント: m を 0 にすることはできません。その場合は 2m = m です。m を 1 にすることはできません。その場合、2 > n > 1 であり、そのような自然数 n は存在しないからです。したがって、言語 M の最短の文字列は aabbb です。より長い文字列の場合、bs の数 n と as の数 m が 2m > n > m を満たすようにする必要があります。

1 の長さの 3 乗の文字列を受け入れるチューリング マシンを作成したいと考えています。しかし、私はこれのためのアルゴリズムを作ることができません。これまでのところ、3 の倍数の長さを受け入れるマシンを作成できます。親切に助けてください

再帰的に列挙可能な文法には制限がないため、LHS に 1 つ以上の終端がある (つまり、非終端がない) プロダクションを作成することは可能ですか?