НГУ

Форумы НГУ
Текущее время: Ср янв 23, 2019 1:23 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 11 ] 
Автор Сообщение
 Заголовок сообщения: Задача по ТА
СообщениеДобавлено: Пн окт 12, 2009 11:03 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Недавно обсуждалась на dxdy.ru Хоррошая заддача!!! :)

Пусть --- регулярный язык и . Всегда ли язык будет регулярным?

Здесь --- алфавит, --- длина слова , --- конкатенация слов и .

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб окт 17, 2009 12:36 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Реакции ноль, задача не пользуется популярностью. Странно, в НГУ столько грамотных программеров :-?

Если что, ответ положительный. Решение пока, наверное, писать рано.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс ноя 08, 2009 9:27 pm 
Не в сети
Частый гость

Зарегистрирован: Пт сен 18, 2009 12:58 pm
Сообщения: 36
Откуда: Андрей
Мне одному кажется, или текст в сообщении не по-русски составлен) точнее составлен то может он и по-русски, вот только TeX формулы в первозданном виде выдаются

_________________
<a href="http://www.nsu.ru/"><img></a>


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс ноя 08, 2009 9:54 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Вс ноя 21, 2004 6:01 pm
Сообщения: 1944
Каким браузером Вы пользуетесь? У меня и в опере и в ie, и в мозилле всё нормально.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб дек 12, 2009 6:36 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Кажись, пришла пора выкладывать решение.

Для произвольных множеств и пусть обозначает множество всех подмножеств множества , а обозначает множество всех функций из в .

Пусть --- детерминированный конечный автомат, распознающий язык . Положим . Далее, пусть , где для любого . Пусть . Наконец, для любой пары из и любого символа пусть , где при всех . Нетрудно показать, что автомат распознаёт язык .

P. S. Насколько "минимальна" описанная конструкция, с ходу судить не возьмусь. В частности, если обозначает число классов -эквивалентности (минимальное число состояний распознающего язык автомата), то я не знаю, при каких найдётся регулярный язык с и . Значение точно не годится, а дальше фиг знает :)

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб янв 30, 2010 12:48 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Пусть и . Через обозначим множество всех слов алфавита , являющихся записями чисел из в системе счисления по основанию . Скажем, что множество является -регулярным, если язык регулярен.

1) Доказать, что для любых множество является -регулярным.

2) Привести пример 3-регулярного множества, которое не является 2-регулярным.

3) Доказать, что множество простых чисел не является -регулярным для любого .

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср окт 19, 2011 5:10 am 
Не в сети
Редкий гость

Зарегистрирован: Ср окт 19, 2011 5:04 am
Сообщения: 2
Коба писал(а):
Пусть и . Через обозначим множество всех слов алфавита , являющихся записями чисел из в системе счисления по основанию . Скажем, что множество является -регулярным, если язык регулярен.

1) Доказать, что для любых множество является -регулярным.

2) Привести пример 3-регулярного множества, которое не является 2-регулярным.

3) Доказать, что множество простых чисел не является -регулярным для любого .

Думаю над 2, что-то вообще без идей.. Точнее, идеи есть, но всё не те, не получается док-ва... Пробовал найти такой заведомо 3-регулярный язык, что эти числа в двоичной будут выглядеть как-нибудь "красиво", построенными по какому-нибудь правилу, но не получилось. Была мысль через лемму о накачке, но не придумал, как применить. Еще вариант с критерием (О бинарном отношении), но там тоже хотелось бы видеть "красивые" числа, поэтому тоже проблемы..
Можете намкнуть, в каком направлении думать?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср окт 19, 2011 9:59 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
lega4 писал(а):
Думаю над 2, что-то вообще без идей.. Можете намкнуть, в каком направлении думать?

Степени тройки :)

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср окт 19, 2011 11:46 am 
Не в сети
Редкий гость

Зарегистрирован: Ср окт 19, 2011 5:04 am
Сообщения: 2
Это была одна из первых мыслей :) Интуитивно вроде понятно, но у меня не получилось формально это доказать, т.к. я не вижу закономерности между степенью тройки и ее разложением по двойкам.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср окт 19, 2011 3:51 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
lega4 писал(а):
Это была одна из первых мыслей :) Интуитивно вроде понятно, но у меня не получилось формально это доказать, т.к. я не вижу закономерности между степенью тройки и ее разложением по двойкам.

Где-то я уже писал формальное доказательство. Поискал здесь на форуме, затем на dxdy.ru - не нашёл. Попробую восстановить с ходу.

Конечно же нужна теорема о накачке. Предполагаем, что язык регулярный и берём достаточно большую степень тройки. В двоичном коде она записывается в виде , и все слова вида будут двоичными записями степеней тройки.

Пусть слово является двоичной записью числа , слово является двоичной записью числа и имеет длину , а слово является двоичной записью числа и имеет длину . Тогда слово является двоичной записью числа . Суммируя геометрическую прогрессию, получаем . Отсюда, учитывая , имеем . Значит, при всех достаточно больших выполняются неравенства . Однако число n больше нуля и при всех отношение есть степень тройки; противоречие.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 28, 2011 6:35 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Добавлю ещё одну задачу про конечные автоматы. Она вроде где-то уже всплывала, но не помню где. Тоже хороша.

Сначала оговорим один ньюанс, важный для нашей задачи. Он касается различия в определении детерминированного конечного автомата, принятого в разных источниках, и его нужно оговорить для того, чтобы задача была чётко сформулирована для всех посетителей форума, в том числе и для тех, кто изучал конечные автоматы не на ММФ НГУ. Те, кто изучал конечные автоматы в рамках курса ТА на первом курсе ММФ НГУ, могут пропустить следующий абзац.

Считаем, что в детерминированном конечном автомате для каждого состояния и каждого символа существует ровно один переход, выходящий из данного состояния и помеченный данным символом. В НГУ на обоих потоках ММФ принято именно такое определение, однако в некоторых книгах встречается определение ДКА, в котором фраза "ровно один переход" заменена на фразу "не более одного перехода". В частности, если ДКА распознаёт некоторый язык , для которого существует такое слово , что при всех словах слово не принадлежит , то этот ДКА должен содержать ловушечные состояния, т. е. состояния, которые достижимы из начального и из которых не достижимо ни одно конечное состояние. (Если рассматривать определения ДКА, в которых фигурирует фраза "не более одного", то ловушечные состояния могут опускаться).

В остальном все определения стандартные.

Задача такая: для каждого натурального придумать такой недетерминированный конечный автомат с состояниями, работающий с символами двухбуквенного алфавита, для которого любой эквивалентный ему (то есть распознающий тот же самый язык) детерминированный конечный автомат содержит не менее чем состояний.

P. S. Задача существенна для понимания того факта, что любой алгоритм преобразования недетерминированного конечного автомата в эквивалентный ему детерминированный имеет не менее чем экспоненциальную сложность. Хотя бы потому, что если на вход такого алгоритма подаётся диаграмма НКА из состояний, работающего с двухсимвольным алфавитом, то длину входа можно ограничить полиномом от , однако длина выхода в некоторых случаях неизбежно будет ограничена снизу числом и, значит, алгоритм потратит экспоненциальное время только на выдачу готового результата.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


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

Часовой пояс: UTC + 7 часов


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

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


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB