字母表「a，b，c」上的所有字符串的語言是否具有相同數量的子字符串「ab」＆「ba」？

字母表「a，b，c」上所有字符串的語言是否與子字符串「ab」相同&「ba」regular？字母表「a，b，c」上的所有字符串的語言是否具有相同數量的子字符串「ab」＆「ba」？

我相信答案是否定的，但很難做出正式的示範，即使是非正式的示範。

關於如何解決這個問題的任何想法？

來源

2011-08-13 Alejandro Barreiro

你應該問那邊http://cstheory.stackexchange.com/。 – Shi

@ Shi-我認爲這個問題對於理論來說太基本了。 cstheory主要是研究級別的主題。 – templatetypedef

顯然不規律。 FA如何識別（abc）^ n c（cba）^ n。這樣的字符串用你的語言，對吧？該論點是基於在不可區別性關係I_l下存在無限多個等價類的事實的簡單論證。

來源

2011-08-13 19:16:27 Patrick87

值得一提的是，這使用了Myhill-Nerode定理，該定理說因爲在可區分關係下存在無限多的等價類，所以語言不能規則。 – templatetypedef

好點。然而，非常直觀的是，如果有無數可區分的字符串，FA將需要無數多個狀態來處理它們。儘管如此。 – Patrick87

證明語言最常用的方法是不正規的使用Pumping Lemmas。

使用引理有點棘手，因爲它具有所有這些「存在」等。要證明一種語言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

whooo！

我將展示證明如何查找「與as和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大量驗證一個字屬於如下到這些語言之一。然而，正則語言是由有限自動機描述的，並且沒有限自動機可以表示表示所有數字所需的無限狀態量。（維基百科文章應該有正式的證明）。

編輯：看起來你可以直不起來了在這種特殊情況下直接使用泵引理：如果你總是讓y是一個字符長，你也沒辦法讓一個詞被停止接受（ABA成爲abbbba沒有區別等）。

只要做了由Patrick87建議的等價類方法 - 它可能會變得比任何骯髒的黑客更乾淨，你需要做的抽水引理適用於這裏。

來源

2011-08-13 18:01:52 hugomg

謝謝，但問題比這更復雜一點。這種語言符合抽水引理。我有一個正式的演示，所以你必須找到其他方法來證明它不規則。演示的主要思想是，如果您擁有屬於該語言的字符串，則可以將其分割爲第一個字符和字符串的其餘部分。通過輸入這個字符，你總會得到一個具有相同數量的ab和ba的字符串，不管第一個字符是a，b還是c。如果您有任何其他想法，請告訴我。感謝和問候，亞歷克斯。 –

實際上，抽象引理可以用於我在我的答案中提名的字符串類型。在這種情況下，基於不可區分性的爭論比覆蓋所有必須嚴格應用PL的情況容易一些。 – Patrick87

@ Patrick87-我只花了大約二十分鐘的時間試圖用抽象引理來證明這種語言並不經常，也沒有成功地這樣做。實際上，我沒有看到你如何將它用於你描述的語言，因爲我總是可以只輸出單個字符'c'而不會使字符串不再有效。你能澄清一下你如何在這裏應用抽象詞？如果我不能很快弄清楚這一點，我會提出一個新的問題，因爲這真的讓我感到困擾。 :-) – templatetypedef

字母表「a，b，c」上的所有字符串的語言是否具有相同數量的子字符串「ab」＆「ba」？

回答

相關問題