Является ли объединение двух нерегулярных языков регулярным?

Question

Учитывая два нерегулярных языка, является ли их объединение регулярным?

Кроме того, почему L = L ₁ ∪ L ₂ = {a ^я b ^j | i, j> = 0} объединение L ₁ = {a ⁱ b ^j | i> = j} и L ₂ = {a ⁱ b ^j | i

Тогда что такое объединение L ₁ = {a ⁱ b ^j | i> j} и L ₂ = {a ⁱ b ^j | я

Answer 1

Учитывая два нерегулярных языка, является ли их объединение регулярным?

Иногда они есть, иногда нет. Возьмем любой нерегулярный язык L. Рассмотрим дополнение этого языка L '. Мы знаем, что L 'нерегулярно, так как регулярные языки закрыты при дополнении (если L' были регулярными, то (L ')' = L также было бы регулярным, противоречие). Поскольку объединение языка и его дополнения является универсальным языком всех строк в алфавите, язык без контекста, безусловно, некоторые пары нерегулярных языков имеют регулярное объединение. Чтобы увидеть, что не все нерегулярные языки имеют регулярное объединение, рассмотрим языки 0 ^ n 1 ^ n и ^ nb ^ n в общем алфавите {0, 1, a, b}. Нетрудно видеть, что объединение этих двух непересекающихся нерегулярных языков не может быть регулярным.

Кроме того, почему L = L1 ∪ L2 = {aibj | i, j> = 0} объединение L1 = {aibj | i> = j} и L2 = {aibj | i

Для всех целых чисел i и j, либо i <= j, либо j <= i (или оба). Отношение <= определяет полный порядок целых чисел. Если дело не в том, что i <= j, мы можем вместо этого написать i> j, чтобы обозначить не (i <= j). Таким образом,> можно рассматривать как своего рода сокращение для отрицания. Поскольку L1 требует i> = j (это тоже просто другой способ записи j <= i), а L2 требует i <j (просто другой способ записи j> i), и потому что j <= i и j> i логическое отрицание друг друга, объединение - которое применяет дизъюнктивный оператор к этим условиям - приводит к тавтологии. Таким образом, результирующее условие всегда истинно - либо i> = j, либо i = 0 к первому совершенно не нужно, предполагая допустимый домен для i и j, и фактически второй и третий языки не упоминают об этом ограничении.

Тогда что такое объединение L1 = {aibj | i> j} и L2 = {aibj | i

Единственными строками, которые не удовлетворяют ни i> j, ни i

1. взять CFG G1 для языка L1
2. взять CFG G2 для языка L2
3. сделать CFG G для языка L, добавив новый начальный символ и произведения, которые производят каждый из начальных символов в G1 и G2 соответственно

Answer 2

Вопрос 1: Является ли объединение двух нерегулярных языков регулярным?

Иногда. Обычные, не зависящие от контекста, контекстно-зависимые, рекурсивные и рекурсивно перечислимые языки закрыты для объединения. Тем не менее, детерминированные c неконтекстные (DCFL) языки, принятые детерминированными c раскрывающимися автоматами (DPDA), не являются. Стандартное доказательство выглядит примерно так. Рассмотрим следующие языки:

L<sub>1</sub> = {a<sup>i</sup>b<sup>j</sup>c<sup>k</sup> : i,j,k ≥ 0}
L<sub>2</sub> = {a<sup>i</sup>b<sup>i</sup>c<sup>j</sup> : i,j ≥ 0}
L<sub>3</sub> = {a<sup>i</sup>b<sup>j</sup>c<sup>j</sup> : i,j ≥ 0}
L<sub>4</sub> = {a<sup>i</sup>b<sup>i</sup>c<sup>i</sup> : i ≥ 0}

Первый язык обычный, второй и третий DCFL, а четвертый не контекстно-свободный . Если DCFL были закрыты при объединении, то поскольку он закрыт при дополнении, язык

L<sub>4</sub><sup>c</sup> = L<sub>1</sub><sup>c</sup> ∪ L<sub>2</sub><sup>c</sup> ∪ L<sub>3</sub><sup>c</sup>

должен быть DCFL. К тому же, L<sub>4</sub> должен быть DCFL. Это противоречие, потому что L<sub>4</sub> даже не зависит от контекста. Следовательно, DCFL не является закрытым для объединения. Наконец, мы можем применить l aws Де Моргана и тот факт, что DCFL закрыт при дополнении, чтобы сделать вывод, что DCFL не закрыт при пересечении.

И наоборот, существуют нерегулярные языки, объединение которых является регулярным. Ответ на ваш второй вопрос показывает, что существуют языки DCFL, объединение которых задается как a*b*.

Вопрос 2: Объединение L<sub>1</sub> = {a<sup>i</sup>b<sup>j</sup> : i ≥ j} и L<sub>2</sub> = {a<sup>i</sup>b<sup>j</sup> : i < j}.

Объединение L<sub>1</sub> и L<sub>2</sub> равно L<sub>3</sub> = {a<sup>i</sup>b<sup>j</sup> : i,j ≥ 0}. Поскольку это равенство с участием множеств, мы должны показать, что L<sub>1</sub> ∪ L<sub>2</sub> ⊆ L<sub>3</sub> и L<sub>3</sub> ⊆ L<sub>1</sub> ∪ L<sub>2</sub>.

1. Если u ∈ L<sub>1</sub> ∪ L<sub>2</sub>, то u ∈ L<sub>1</sub> или u ∈ L<sub>2</sub>. Если u ∈ L<sub>1</sub>, то u = a<sup>i</sup>b<sup>j</sup>, где i ≥ j. Если u ∈ L<sub>2</sub>, то u = a<sup>i</sup>b<sup>j</sup>, где i < j. По трихотомии u = a<sup>i</sup>b<sup>j</sup>, где i,j ≥ 0. Таким образом, u ∈ L<sub>3</sub>.
2. Если u ∈ L<sub>3</sub>, то u = a<sup>i</sup>b<sup>j</sup>, где i,j ≥ 0. По трихотомии либо i ≥ j, либо i < j. Если первое, то u ∈ L<sub>1</sub>. Если последнее, то u ∈ L<sub>2</sub>. Таким образом, u ∈ L<sub>1</sub> ∪ L<sub>2</sub>.

Вопрос 3: Объединение L<sub>1</sub> = {a<sup>i</sup>b<sup>j</sup> : i > j} и L<sub>2</sub> = {a<sup>i</sup>b<sup>j</sup> : i < j}

Объединение L<sub>1</sub> и L<sub>2</sub> это набор строк a<sup>i</sup>b<sup>j</sup>, где i < j или i > j. Это эквивалентно тому, что i ≠ j по трихотомии. Следовательно, L<sub>1</sub> ∪ L<sub>2</sub> = {a<sup>i</sup>b<sup>j</sup> : i ≠ j}.