Являются ли контекстно-свободные языки в

Языки без контекста не закрыты в дополнении, мы это знаем.

Насколько я понимаю, контекстно-свободные языки, которые являются подмножеством $a^*b^*$ для некоторых букв $a,b$ , закрыты в дополнении (!?)

Вот мой аргумент. Каждый CF язык $L$ имеет полулинейный образ Париха $\pi(L) = \{ (m,n) \mid a^mb^n \in L \}$ . Полулинейные множества замкнуты относительно дополнения. Множество векторов, представляющих полулинейное множество, может быть легко преобразовано в линейную грамматику.

Вопрос. Есть ли легкодоступная ссылка на этот факт?

Технически эти языки называются ограниченными , т. Е. Подмножеством $w_1^* \dots w_k^*$ для некоторых слов $w_1,\dots,w_k$ .

Моя мотивация для этого вопроса взята из недавнего вопроса о свободе контекста $\{ a^nb^m \mid n^2 \neq m \}$ . Его дополнение внутри $a^*b^*$ кажется более простым в обращении.

Эта характеристика ограниченных контекстно-свободных языков обусловлена ​​Гинзбургом («Математическая теория контекстно-свободных языков») и появляется в следствии 5.3.1 в его книге. Для общего существуют некоторые ограничения на полулинейные множества, но при k ≤ 2 эти ограничения всегда выполняются, и поэтому нетрудно сделать вывод, что дополнение такого языка (в пределах w ∗ 1 w ∗ 2 ) не зависит от контекста ,$k$$k \leq 2$$w_1^* w_2^*$

Гинзбург упоминает эти последствия в своей книге.

Следствие 5.6.1 Если и M 2 являются [контекстно-свободными] языками, w 1 и w 2 словами, то M 1 ∩ M 2 является [контекстно-свободным] языком.$M_1 \subseteq w_1^*w_2^*$$M_2$$w_1$$w_2$$M_1\cap M_2$

Следствие 5.6.2 Если и M 2 являются [контекстно-свободными] языками, w 1 и w 2 словами, то M 1 - M 2 и M 2 - M 1 являются [контекстно-свободными] языки.$M_1 \subseteq w_1^*w_2^*$$M_2$$w_1$$w_2$$M_1 - M_2$$M_2-M_1$

Другое доказательство использует следующую характеристику, доказанную в этом ответе :

Язык зависит от контекста, если A определима в арифметике Пресбургера.$\{ a^i b^j : (i,j) \in A \}$$A$

Очевидно , определимо в Пресбургере арифметических тогда и только тогда ¯ определим в Пресбургере арифметике.$A$$\overline{A}$

$L_i \subseteq a^*b^*$