言語を見ただけでその言語が規則的かどうかを推測するトリックはありますか?
証明方法を選択するには、まず仮説を立てる必要があります。長い問題を解くのにかかる時間を短縮するために必要なヒント/パターンを知っていますか?
たとえば、言語が規則的であり、DFA/文法を構築したくない場合、補題のポンピングに時間を費やさないようにするためです。
例えば：
1. L={w ε {a,b}*/no of a in (w) < no of b in (w)}
2. L={a^nb^m/n,m>=0}
上記の例を見るだけで、どちらが規則的かを判断する方法は??
一般に、言語を見るとき、その言語が規則的かどうかを判断するための良い経験則は、文字列を読み取って「この文字列は言語に含まれているか?」という質問に答えることができるプログラムを考えることです。
このようなプログラムを作成するには、変数に任意の値を格納する必要がありますか?それとも、プログラムの状態 (つまり、可能なすべての変数の値の組み合わせ) が有限の固定数の可能性に制限されているのでしょうか? 固定数の値のみを持つことができる固定数の変数のみを必要とするプログラムでその言語を認識できる場合、通常の言語を使用できます。そうでない場合は、そうではありません。
これを使用すると、第 1 言語は規則的ではありませんが、第 2 言語は規則的であることがわかります。a第一言語では、私が見た の数と の数を覚えておく必要がありますb。(または、少なくとも、(# of as) - (# of bs) を追跡し、そのカウントが負のときに文字列が終了した場合に受け入れる必要があります)。同時に、 の数に制限がないaため、この数は任意に大きくなる可能性があります。
第二言語では、私は何nを気にしませんm。bしたがって、2 番目の言語では、私のプログラムは「少なくとも 1 つ以上見たことがありますか?」を追跡するだけです。a最初の の後に出現する文字がないことを確認しますb。(したがって、2 つの値のみを持つ 1 つの変数 - true または false)
したがって、言語 1 を通常の言語にする 1 つの方法は、次のように変更することです。
1. L={w ∈ {a,b}*/no of a in (w) < no of b in (w), and no of a in (w) < 100}
aこれで、 100 に達したら見た s の数を追跡する必要がなくなりました (文字列が言語に含まれていないことが自動的にわかるためb) 。as の数自体が大きすぎない限り、それで十分だとわかっているので、カウントを停止できます。
aこれに関して注意すべき一般的なケースの 1 つは、「 s の数が 13 の倍数である」または「w ∈ {0,1}* で、wが 13 の倍数のバイナリ表現である」という言語について尋ねられた場合です。 . これらを使用すると、決定を行うために整数を追跡する必要があるように見えるかもしれませんが、実際には必要ありません。どちらの場合も、0 から 12 までカウントできる変数を保持するだけで済みます。 「複数の」タイプの言語のアウト。(そして関連する「奇数」または「偶数」または「13 の倍数よりも 1 大きい」)
ただし、他の数学的特性 (たとえば、w ∈ {0,1}* でwは完全平方のバイナリ表現) は、非正規言語になります。