2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Является ли дополнение к языку контекстно-свободным?
Сообщение09.12.2016, 10:32 


05/12/13
26
Рассмотрим язык $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$ контекстно-свободный.

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

 Профиль  
                  
 
 Re: Является ли дополнение к языку контекстно-свободным?
Сообщение09.12.2016, 14:49 


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

 Профиль  
                  
 
 Re: Является ли дополнение к языку контекстно-свободным?
Сообщение10.12.2016, 11:30 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Замысел верный, но исполнение, имхо, хромает. Вот хотелось бы посмотреть на магазинный автомат распознающий язык
AVV в сообщении #1175355 писал(а):
Слова, в которых количество c не совпадает с количеством a, следующих после хотя бы одной b

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

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

 Профиль  
                  
 
 Re: Является ли дополнение к языку контекстно-свободным?
Сообщение13.12.2016, 22:47 


05/12/13
26
whitefox в сообщении #1175612 писал(а):
Замысел верный, но исполнение, имхо, хромает. Вот хотелось бы посмотреть на магазинный автомат распознающий язык
AVV в сообщении #1175355 писал(а):
Слова, в которых количество c не совпадает с количеством a, следующих после хотя бы одной b


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

 Профиль  
                  
 
 Re: Является ли дополнение к языку контекстно-свободным?
Сообщение14.12.2016, 22:20 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Является ли дополнение к языку контекстно-свободным?
Сообщение15.12.2016, 07:35 


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

Собственно, можно так построить рассуждение. Заметим, что слова из языка $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$ уже не хватает возможностей. Т.е. всегда не хватает возможностей только на одну какую-то штуку. А каковы слова из дополнения? Это те слова, для которых не выполнена хотя бы одна "штука". Вот и перечисляем аккуратно все "штуки" и пишем МП-автомат для них.

 Профиль  
                  
 
 Re: Является ли дополнение к языку контекстно-свободным?
Сообщение15.12.2016, 11:21 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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\}$ оба КС, следовательно и их конкатенация тоже КС.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group