識別常規語言

我很難識別常規語言。識別常規語言

我知道，如果R是一個正則語言然後如果A = RR，由於爲R的串聯因此A爲正則語言

但是B = {WW | w < - R}定期？

我的第一個直覺是肯定的。因爲它也是R的串聯。但是因爲它是串聯的一個子集，所以我覺得我不能以這種方式證明它。然後我在想，因爲w是一個正則語言的字符串，它是單體的連接，然後是它們的連接......我知道我已經完全脫離了軌道，因爲如果這樣想，那不是什麼？現在我更傾向於說它不是。因爲我真的找不到它的正則表達式。我想嘗試使用抽象引理，但很難適用於這個例子。

任何人都可以提供一些建議嗎？即使是正確的軌道讓我遵循將是偉大的？

來源

2011-10-23 lynnyilu

繼續嘗試抽吸引理。先從一個非常簡單的正則表達式，例如：

R = ab*

因爲此時你正試圖證明它是不規律的，你需要的是一個反例。所以你可以選擇任何你想要的R。（以上都可以正常工作。）

來源

2011-10-23 08:24:16

謝謝你的幫助！我工作過，只能確認我的推理，因爲我懷疑它：如果R = ab *和w <-R， B = {ww | w <-R}不是（a^p）b（a^p）b < - B的長度大於p的長度，因此如果我們假設它是，並且p是抽吸長度，則通過抽吸引理（a^p）b^p）b = xyz，其中xy^iz在B中對於所有i> = 0，因爲| xy | y =完全由'a'組成。但然後xyyz不在D所以這是一個矛盾因此，它不是正規的 – lynnyilu

看起來不錯（我不得不檢查抽水引理，這是一段時間...） –

哈哈聽起來好吧是夠好的。謝謝 – lynnyilu

識別常規語言

回答

相關問題