アルファベット "a、b、c"の部分文字列 "ab"＆ "ba"と同じ数のすべての文字列の言語が標準ですか？

Question

"ab" & "ba"と同じ数の部分文字列を持つアルファベット "a、b、c"のすべての文字列の言語ですか？

答えはNOだと思いますが、非正式なデモであっても正式なデモを行うのは難しいです。

これにアプローチする方法についてのご意見はありますか？

Answer 1

明らかに正規ではありません。 FAが（abc）^ n c（cba）^ nをどのように認識するか。このような文字列はあなたの言葉になりますよね？議論は、区別不能関係I_lの下に無限に多くの等価クラスが存在するという事実に基づく単純なものである。

Answer 2

言語を証明する最も一般的な方法は、普通ではなく、Pumping Lemmasを使用していることです。

補助定理を使うのは少し複雑ですが、それはすべて「存在する」などです。言語を証明するためには、ポンピング補題を使って規則的でないことを証明する必要があります。

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 

whooo！

私は校正校がどのように「同じ数のbs」の言語を探すかを示します。あなたのケースに変換しstraighfowardする必要があります。

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. 

---

あなたはこの作業の理由で直感が必要な場合は単語が属している場合、それはあなたが確認するために、多数のarbritrarilyするためにカウントできるようにする必要がありますどのように次のこれらの言語のいずれかにしかし、正規言語は有限オートマトンによって記述され、有限オートマトンはすべての数値を表現するのに必要な無限大状態を表すことはできません。 （ウィキペディアの記事は正式な証明が必要です）。限り、あなたは（ABAがabbbbaになって言葉が受け入れられて停止させることはできませんあなたはいつもyを作る場合は1つの文字である：

---

EDIT：あなたがまっすぐに直接この特定のケースでは、ポンピング補題を使用することはできませんように見えます違いはありません）。

パトリック87で提案されている等価クラスのアプローチを実行してください。ポンピング補助定理をここで適用できるようにするために必要な汚れたハッキン​​グのいずれよりもきれいになるでしょう。