НГУ

Недавно обсуждалась на dxdy.ru Хоррошая заддача!!!

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

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

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

Реакции ноль, задача не пользуется популярностью. Странно, в НГУ столько грамотных программеров

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

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

Мне одному кажется, или текст в сообщении не по-русски составлен) точнее составлен то может он и по-русски, вот только TeX формулы в первозданном виде выдаются

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

Каким браузером Вы пользуетесь? У меня и в опере и в ie, и в мозилле всё нормально.

Кажись, пришла пора выкладывать решение.

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

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

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

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

Пусть и . Через обозначим множество всех слов алфавита , являющихся записями чисел из в системе счисления по основанию . Скажем, что множество является -регулярным, если язык регулярен.

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

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

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

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

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

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

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

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

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

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

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

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

Добавлю ещё одну задачу про конечные автоматы. Она вроде где-то уже всплывала, но не помню где. Тоже хороша.

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

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

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

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

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

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