封閉性

Question

我有以下問題：

語言L1 = {A^N * B^N：N> = 0}和L2 = {B^N * A^N： N> = 0}是 上下文無關語言，以便它們在L1L2下關閉，從而L = {A^N * b^2N甲^ N：N> = 0}，因爲它是由一個 產生必須是自由的太上下文關閉屬性。

我要證明，如果這是真的還是假的。 所以我檢查了L語言，我不認爲它是上下文無關的，那麼我也看到L2只是L1顛倒了。

我一定要檢查是否L1，L2是確定的？

Answer 1

L1 = {A ^Ñ b ^Ñ：N> = 0}和L2 = {B ^Ñ一個^Ñ：N> = 0}都是 上下文無關。

由於上下文無關語言下級聯關閉，L3 = L1L2也是上下文無關。

然而，L3是不相同的語言L4 = {A ^Ñ b ^2N一個^Ñ：N> = 0}。 字符串abbbaa在L3中，但不在L4中。

所以是L4上下文？如果是這樣，它必須服從pumping lemma for context-free languages。

令P爲L4的泵送長度。選擇S =一個^p b ^2P一個^p。 然後s在L4中，並且| s | > p。因此，如果L4沒有上下文，我們可以使用uvxyz來編寫s ，| vxy | < = p，| vy | > = 1，和UV ^Ñ XY ^Ñ z是在L4爲 任意n> = 0

遵守L4任何非空字符串的下述特性：a的的計數等於B的計數。子字符串'ab'恰好有一次出現，並且子字符串'ba'恰好發生了一次 。 a的最初字符串的長度等於a的最後一個字符串的長度。

我們可以用這些意見來約束v和y的可能選擇在我們的L4抽的說法。既不v或y可以包含子串「AB」，因爲那樣的話，爲v和y泵送任意次數，輸出串將包含「AB」的多次出現，並且因此不能L4的元素。相同的論點適用於子字符串'ba'。

所以v必須是要麼是空，全部的，或全部B的。這同樣適用於y。

此外，如果v是全部的，那麼y必須由相同數目的B的組成;否則，泵串將包含數量不等的A和B的，因爲V和Y是由 相同的N泵。同樣，如果v都是b，那麼y必須是a的相同數量。

但是，如果v是a，y都是b，則a的最後一個串不受v和y影響，因此a的前導字符串將不再與a的尾部字符串匹配。 類似地，如果v是全部b並且y是全部a，則隨着v和y被泵送，a的前導和尾隨串將再次具有不同的長度。

v和y不能都是空的，因爲這會違反條件| vy | > = 1爲 CFL抽吸引理。但是由於我們已經確定| v | = | y |，它遵循 v和y都不能爲空。

但是，如果V不能爲空，也不能是全部的，不能全是B的，而不能包含 子串「AB」或「BA」，再有就是uvxyz沒有可能的選擇。這 的泵版本s仍然在L4。因此L4不是上下文無關的。

Answer 2

我不知道它是什麼 - 請注意，在L1和L2的每一個定義中，n都在該定義範圍內，即它們是兩個不同的變量。當你把他們應重命名一個，並得到相反：

L = {a^n * b^n b^m * a^m : n,m>=0} 

這是從你的L一個非常不同的語言，但它顯然是一個免費的背景之一。