Является ли следующий союз КЛЛ и КЛЛ не-КЛЛ сам? - PullRequest
Новая
       2

Является ли следующий союз КЛЛ и КЛЛ не-КЛЛ сам?

2 голосов
/ 22 февраля 2012

Я ТА, и студент спросил меня о следующем.Смущающе, я не смог придумать ответ, поэтому я обращаюсь к вам, ребята.

Мы знаем, что L_1 = {a ^ nb ^ nc ^ n} не-CFL.Мы также знаем, что L_2 = {a ^ ib ^ kc ^ j: i! = K} не зависит от контекста.

Как насчет объединения этих?(это явно нерегулярно) Является ли это контекстно-свободным?

1 Ответ

3 голосов
/ 22 февраля 2012

Мы выбираем в качестве нашей вселенной язык U = {a ^ i b ^ j c ^ k | i, j, k в N}.

Тогда L_1 ^ C = {a ^ i b ^ j c ^ k | i! = j или j! = k} = {a ^ i b ^ j c ^ k | i! = j} union {a ^ i b ^ j c ^ k | j! = k} = L_A объединение L_B. Обратите внимание, что L_A = L_2.

По ДеМоргану, L_1 объединение L_2 = (L_1 ^ C пересекается с L_2 ^ C) ^ C = ((L_A объединение L_B) пересекается с L_2 ^ C) ^ C, что по закону распределения ((L_A пересекается с L_2 ^ C) объединение (L_B пересекаются с L_2 ^ C)) ^ C.

Напомним, что, поскольку L_A = L_2, мы получаем (L_B пересекается с L_2 ^ C) ^ C. С помощью DeMorgan мы можем отобразить это как L_B ^ C union L_2. Мы уже признали, что L_2 не зависит от контекста. Дополнение L_B в нашей вселенной: {a ^ i b ^ j c ^ k | j = k}, который также не зависит от контекста. Объединение двух контекстно-свободных языков также не зависит от контекста, так что да, L_1 union L_2 не зависит от контекста.

Пройдя через формальности, интуиция очевидна: L_1 объединение L_2 эквивалентно тому, чтобы сказать, что либо i! = J (число a и b различно), либо количество b и c одинаково. Если вы подумаете об этом, это прекрасно отражает требования языков: если i! = J, мы в порядке по второй части; единственный способ не попасть в L_2 - это если мы уже точно знаем, что i = j, и нам нужно только заботиться о гарантии j = k.

В логической логике: (a и b) или (не a) эквивалентны (b или (не a)).

CFG для языка является следующим: 

S := A | C
A := aA | B
B := lambda | bBc
C := Cc | D | E
D := a | aD | aDb
E := b | Eb | aEb

Вы можете получить КПК с помощью конструкций синтаксического анализатора сверху вниз или снизу вверх.

...