Закрытие свойства контекстно-свободных языков

Question

У меня есть следующая проблема:

Языки L1 = {а^п * б^п: п> = 0} и L2 = {Ь^п * а^п: n> = 0} - это контекстные свободные языки, поэтому они закрываются под L1L2, поэтому L = {a^n * b^2n A^n: n> = 0} также должно быть свободным от контекста, потому что оно генерируется с помощью свойство закрытия.

Я должен доказать, верно это или нет. Итак, я проверил L-язык, и я не думаю, что это контекст свободен, тогда я также видел, что L2 просто перевернут L1.

Должен ли я проверить, детерминированы ли L1, L2?

Answer 1

L1 = {а п б ^п: п> = 0} и L2 = {Ь ^пп: N> = 0} оба контекст бесплатно.

Поскольку контекстные языки закрыты под конкатенацией, L3 = L1L2 также не содержит контекста.

Однако L3 не тот же язык, как L4 = {а ^п б ^2nп: п> = 0}. Строка abbbaa находится в L3, но не L4.

То есть L4 не имеет контекста? Если это так, он должен подчиняться pumping lemma for context-free languages.

Пусть p - длина прокачки L4. Выберите s = a ^p b ^2p a ^p. Тогда s находится в L4 и | s | > p. Поэтому, если L4 не имеет контекста, мы можем написать s как uvxyz, с | vxy | < = p, | vy | > = 1, и УФ-^п х ^п г в L4 для любого п> = 0.

соблюдать следующие свойства любой непустой строки в L4: Количество в й равен коле-Б. Существует ровно одно вхождение подстроки 'ab' и ровно одно из вхождения подстроки 'ba'. Длина начальной строки a равна длине конечной строки a.

Мы можем использовать эти наблюдения для ограничения возможных вариантов v и y в нашем аргументе накачки для L4. Ни v, ни y не могут содержать подстроку «ab», потому что тогда, когда v и y накачиваются произвольным числом раз, выходная строка будет содержать несколько вхождений «ab» и, следовательно, не может быть элементом L4. Тот же аргумент применяется к подстроке «ba».

Таким образом, v должно быть либо пустым, либо всем, либо всем b. То же самое относится к y.

Кроме того, если v - все a, то y должно состоять из одного и того же числа b; в противном случае перекачиваемая строка будет содержать неравные числа a и b, так как v и y накачиваются на тем же n. Аналогично, если v - все b, то y должно быть одинаковым числом a.

Но если v - все a, а y - все буквы b, окончательная строка a не подвержена перекачке v и y, поэтому ведущая строка a больше не будет соответствовать завершающей строке. Аналогично, если v - все буквы b, а y - все a, то ведущая и конечная строки a снова будут иметь разную длину при перекачке v и y.

v и y не могут быть пустыми, поскольку это нарушит условие | vy | > = 1 для леммы прокачки CFL. Но так как мы установили, что | v | = | y |, следует, что ни v, ни y не могут быть пустыми.

Но если v не может быть пустым, не может быть все а, не может быть все б, и не может содержать подстроки «AB» или «ба», то нет никакой возможности выбора uvxyz, для которых перекачиваемой версия s все еще находится в L4. Поэтому L4 не является контекстно-свободным.

Answer 2

Я не уверен, что это - обратите внимание, что в каждом из определений из L1 и L2, n является область действия в пределах этого определения, то есть они являются два разными переменными. Когда вы объедините их, вы должны переименовать один, и получить вместо:

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

Это очень отличается от языка вашего L, но это, очевидно, контекст бесплатно один.