Является ли дополнение к языку контекстно-свободным?

[AVV]

Рассмотрим язык $L = \{a^n b^{n+m} c^m a^m | n,m \ge 0\}$. Является ли его дополнение контекстно-свободным?

Мне кажется, что да, так как, вроде бы, можно представить $\bar L$ как объединение следующих языков:

1. Слова, в которых количество c не совпадает с количеством a, следующих после хотя бы одной b;
2. Слова, в которых количество b отлично от количества предшествующих a плюс последующих c;
3. Слова с "неправильным" порядком букв: $\{a^i b^j c^k a^l b^p c^q w | q \ge 1 \lor q \ge 1\}$, $\{a^i b^j a^k w | k \ge 1\}$, $\{a^i c^j w | j \ge 1\}$.

Для вышеперечисленных языков можно построить магазинный автомат, поэтому они контекстно-свободны. А тогда и $\bar L$ контекстно-свободный.

Не упускаю ли я чего-нибудь?

[AVV]

Явно надо бы добавить
4. Слова, в которых количество b отлично от количества начальных a плюс количество a в конце.

[whitefox]

Замысел верный, но исполнение, имхо, хромает. Вот хотелось бы посмотреть на магазинный автомат распознающий язык

AVV в сообщении #1175355 писал(а):

Слова, в которых количество c не совпадает с количеством a, следующих после хотя бы одной b

Рассмотрим произвольную непустую цепочку $w$ в алфавите $\Sigma=\{a,b,c\}.$ Максимальную непустую подцепочку из одинаковых букв будем называть сегментом цепочки $w.$ Всякая непустая цепочка в алфавите $\Sigma$ состоит из нескольких сегментов. Положим по определению, что пустая цепочка является нульсегментной.

1. Определите из скольких сегментов могут состоять слова языка $L.$ Очевидно, что слова с иным числом сегментов принадлежат языку $\overline{L}$ и, что язык этих слов является регулярным, а потому и КС. Постройте регулярное выражение для этого языка.
2. Вы верно подметили, что слова языка $L$ имеют вполне определённый порядок сегментов. Очевидно, что слова с иным порядком принадлежат языку $\overline{L}$ и, что язык этих слов является регулярным, а потому и КС. Постройте регулярное выражение для этого языка.
3. Оставшиеся слова языка $\overline{L}$ представьте в виде объединения конечного числа языков. Покажите, что эти языки КС, построив соответствующие магазинные автоматы. Если это возможно.

[AVV]

whitefox в сообщении #1175612 писал(а):

Замысел верный, но исполнение, имхо, хромает. Вот хотелось бы посмотреть на магазинный автомат распознающий язык

AVV в сообщении #1175355 писал(а):

Слова, в которых количество c не совпадает с количеством a, следующих после хотя бы одной b

А в чём загвоздка? Сначала находимся в состоянии, в котором принимаем a и c. Получив b переходим в другое состояние, в котором, получив a "сокращаем" её с c, если на вершине стека оно; иначе кладём a в стек, так, что избыток a-шек будет на вершине. То же, с точностью до наоборот, с b.

[whitefox]

Загвоздка в том, что описанный Вами магазинный автомат допускает по пустому магазину не Ваш язык , а его дополнение. А дополнение КС-языка не обязано само быть КС-языком.

[AVV]

Но ведь я же и хочу описать дополнение. То, что КС-языки не замкнуты относительно дополнения -- это понятно.

Собственно, можно так построить рассуждение. Заметим, что слова из языка $L$ -- это слова, для которых выполнено одновременно:
1. Правильный порядок сегментов.
2. Между a и c столько b, сколько их в сумме.
3. Количество c и a после b равно их сумме.
4. Количество первых и последних a равно количеству b.
Слова из дополнения -- слова, для которых не выполнен хотя бы один пункт. Т.о. дополнение -- объединение языков $L_i$, для слов из которых выполнено отрицание $i$. Такие языки явно КС, т.к. предъявляется МП-автомат.

Наводящее соображение, почему дополнение контекстно-свободно. Если пытаться строить магазинный автомат, порождающий исзодный язык, всегда будет чуть-чуть не получаться: например, $a^n b^{n+m} c^m$ сделать можно, но на $a^m$ уже не хватает возможностей. Т.е. всегда не хватает возможностей только на одну какую-то штуку. А каковы слова из дополнения? Это те слова, для которых не выполнена хотя бы одна "штука". Вот и перечисляем аккуратно все "штуки" и пишем МП-автомат для них.

[whitefox]

AVV в сообщении #1177069 писал(а):

Но ведь я же и хочу описать дополнение.

Имелось ввиду не дополнение языка $L,$ а дополнение языка

AVV в сообщении #1175355 писал(а):

Слова, в которых количество c не совпадает с количеством a, следующих после хотя бы одной b;

Предложенный Вами автомат допускает по пустому магазину дополнение к этому языку, а не сам этот язык.

AVV в сообщении #1177069 писал(а):

Слова из дополнения -- слова, для которых не выполнен хотя бы один пункт. Т.о. дополнение -- объединение языков $L_i$, для слов из которых выполнено отрицание $i$. Такие языки явно КС, т.к. предъявляется МП-автомат.

Предъявляются ли? В конечном счёте всё сведётся к предъявлению МП-автомата допускающего язык $\{x^iy^j\mid i>0, j>0, i\ne j\}.$ У Вас такой есть?

AVV в сообщении #1177069 писал(а):

Если пытаться строить магазинный автомат, порождающий исзодный язык, всегда будет чуть-чуть не получаться:

Это потому, что язык $L$ является конкатенацией языков $L_1=\{a^nb^n\mid n\geqslant0\}$ и $L_2=\{b^mc^ma^m\mid m\geqslant0\}$ из которых первый КС, а второй нет.

AVV в сообщении #1177069 писал(а):

например, $a^n b^{n+m} c^m$ сделать можно

А это потому, что языки $\{a^nb^n\mid n\geqslant0\}$ и $\{b^mc^m\mid m\geqslant0\}$ оба КС, следовательно и их конкатенация тоже КС.