НГУ
http://forum.nsu.ru/

Задача по ТА
http://forum.nsu.ru/viewtopic.php?f=24&t=20522
Страница 1 из 1

Автор:  Коба [ Пн окт 12, 2009 11:03 pm ]
Заголовок сообщения:  Задача по ТА

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

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

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

Автор:  Коба [ Сб окт 17, 2009 12:36 pm ]
Заголовок сообщения: 

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

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

Автор:  sliper [ Вс ноя 08, 2009 9:27 pm ]
Заголовок сообщения: 

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

Автор:  N.Ch. [ Вс ноя 08, 2009 9:54 pm ]
Заголовок сообщения: 

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

Автор:  Коба [ Сб дек 12, 2009 6:36 pm ]
Заголовок сообщения: 

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

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

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

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

Автор:  Коба [ Сб янв 30, 2010 12:48 am ]
Заголовок сообщения: 

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

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

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

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

Автор:  lega4 [ Ср окт 19, 2011 5:10 am ]
Заголовок сообщения: 

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

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

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

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

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

Автор:  Коба [ Ср окт 19, 2011 9:59 am ]
Заголовок сообщения: 

lega4 писал(а):
Думаю над 2, что-то вообще без идей.. Можете намкнуть, в каком направлении думать?

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

Автор:  lega4 [ Ср окт 19, 2011 11:46 am ]
Заголовок сообщения: 

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

Автор:  Коба [ Ср окт 19, 2011 3:51 pm ]
Заголовок сообщения: 

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

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

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

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

Автор:  Коба [ Пт окт 28, 2011 6:35 pm ]
Заголовок сообщения: 

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

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

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

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

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

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

Страница 1 из 1 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/