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

Question

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

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

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

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

Answer 1

L1 = {aⁿ bⁿ: n> = 0} и L2 = {bⁿ aⁿ: n> = 0} не зависят от контекста.

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

Однако L3 - это не тот же язык, что и L4 = {aⁿ b²ⁿ aⁿ: n> = 0}. Строка abbbaa находится в L3, но не в L4.

Так L4 не зависит от контекста? Если это так, он должен подчиняться накачанной лемме для контекстно-свободных языков.

Пусть p - длина накачки L4. Выберите s = a^p b^2p a^p. Тогда s находится в L4, и |s| > стр. Поэтому, если L4 не зависит от контекста, мы можем написать s как uvxyz, с |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 должно быть пустым, все a или все b. То же самое относится к у.

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

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

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

Но если v не может быть пустым, не может быть всеми a, не может быть всеми 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, но это, очевидно, контекстно-свободный.