Пусть L1 = {a^nb^mc^(n + m)/n, m> 0} и L2 = {a^nb^nc^m/n, m> 0}. L3 = L1 ∩ L2 контекстно- бесплатно или нет?

Question

Пусть L1 = {a^nb^mc^(n + m)/n, m> 0} и L2 = {a^nb^nc^m/n, m> 0}. L3 = L1 ∩ L2 контекст -бесплатно или нет?

Мое логическое существо, если n < m, пересечение даст язык (a^nb^nc^n), если n> m, пересечение даст язык (a^nb^mc^m) в обоих случаях есть CFG, так верно ли моя интерпретация?

Answer 1

Я не уверен, правильно ли я понял вашу идею, но если вы попытаетесь использовать те же n и m для L1 и L2 и вычислите пересечение на основе этого, вы не правы.

Кроме того, язык {^п б^п с^п | n> 0} не является CFG, как вы можете видеть в качестве примера здесь https://en.wikipedia.org/wiki/Context-free_language или показать с помощью леммы о перекачке.

Как можно увидеть, что выглядит L1 ∩ L2?
x ∈ L1 ∩ L2 < => x ∈ L1 и x ∈ L2. Таким образом, x должен заполнить оба ограничения двух языков.
Поэтому х ∈ L1 ∩ L2 представляет собой х = ^п б^м с^о где п = т из-L2 и о = п + т = п + п (п + т из-за L1 и n + n, поскольку n = m).
Это дает нам L1 ∩ L2 = {^в п б^н гр²ⁿ | n> 0}, что не является CFG.

Причина:

• Наглядно говоря CFG не может рассчитывать (более чем один раз, ^п б^п отлично). Но для достижения паттерна n, n, 2n, мы должны посчитать amoung a и b, а затем добавить нужное количество c.
• Насосное леммой: Мы должны свести исходную лемму для того, чтобы показать, что {^п б^п с²ⁿ | n> 0} не является CFG.Таким образом, мы должны доказать, что для любого р> = 0 существует s ∈ {^п б^п с²ⁿ | n> 0}, которые НЕ могут быть разделены на uvwxy fullfilling | uvw | < = р и и v^к ш х к у ∈ { п б^нс 2n | n> 0}.
  
  Доказательство: Учитывая, р> = 0. Выберем слово T = ^р б^р с^2р ∈ L1 ∩ L2. Теперь для каждого выбора uvwxy = t мы не можем перекачивать uvwxy до сих пор ∈ L1 ∩ L2. Это связано с тем, что мы перекачиваем только v и x. И | vwx | < = p. Таким образом, vwx не может содержать a, b и c, но не более двух из них. Теперь, если мы качаем v и х мы получаем больше, чем с, или наоборот, и в результате у v ш х у не в L1 ∩ L2.