同じ数の部分文字列「ab」と「ba」を持つアルファベット「a、b、c」上のすべての文字列の言語は規則的ですか？
答えはノーだと思いますが、正式なデモンストレーションでなくても、正式なデモンストレーションを行うことは困難です。
これにアプローチする方法について何かアイデアはありますか？
2 に答える
2
それは明らかに定期的ではありません。FAは（abc）^ nc（cba）^nをどのように認識しますか。このような文字列はあなたの言語ですよね？議論は、区別できない関係I_lの下に無限に多くの同値類があるという事実に基づく単純なものです。
于 2011-08-13T19:16:27.690 に答える
0
言語が規則的でないことを証明する最も一般的な方法は、PumpingLemmasを使用することです。
補題を使用することは、それらすべてが「存在する」などであるため、少し注意が必要です。言語Lが正規言語の反復補題を使用して規則的でないことを証明するには、次のことを証明する必要があります。
for any integer p,
there is a word w in L of length n, with n>=p, such that
for all possible ways to decompose w as xyz, with len(xy) <= p and y non empty
there exists an i such that x(y^i)z (repeating the y bit i times) is NOT in L
おっと！
証明が「同じ数のasとbs」言語をどのように探すかを示します。あなたのケースに変換することはまっすぐ進むべきです：
for any given p, we can make a word of length n = 2*p
a^p b^p (p a's followed by p b's)
any way you decompose this into xyz w/ |xy| <=p, y will only contain a's.
Thus, pumping the the y part will make the word have more as than bs,
thus NOT belonging to L.
これが機能する理由を直感的に理解する必要がある場合は、単語がこれらの言語のいずれかに属しているかどうかを確認するために、任意に大きな数を数える必要がある方法からわかります。ただし、正規言語は有限オートマトンで記述されており、すべての数値を表すために必要な無限の状態を表すことができる有限オートマトンはありません。（ウィキペディアの記事には正式な証明が必要です）。
編集：この特定のケースでは、ポンピング補題を直接使用することはできないようです。常にy1文字の長さにすると、単語の受け入れを停止することはできません（abaがabbbbaになっても違いはありませんなど）。
Patrick87によって提案された同値類のアプローチを実行するだけです。おそらく、ここでポンピング補題を適用できるようにするために必要なダーティハックよりもクリーンであることがわかります。
于 2011-08-13T18:01:52.217 に答える