Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Рыцари, которые говорят только правду, и лжецы, которые всегда лгут, выстроились в ряд. (В ряду хотя бы один человек). Каждый из них произнёс фразу «Все мои соседи лжецы». Обозначим рыцаря буквой Р, а лжеца — буквой Л. Тогда каждой последовательности рыцарей и лжецов, для которой выполняется условие задачи, соответствует некоторое слово.
Опишите это слово, используя формулу, которая называется регулярным выражением. Такое выражение строится с помощью описываемых ниже операций "итерация", "умножение", "сложение".
Так для повторения блока из нескольких букв используйте операцию «звездочка» (итерация), например, (abb)* задает множество слов {пустое слово, abb, abbabb, abbabbabb, …}. Умножение множеств (эту операцию, как обычно в алгебре, изображают точкой приписыванием второго операнда вслед за первым, что мы и будем делать), описывает склейку всех слов первого множества со словами второго (третьего и т.д.), например a*cb* обозначает множество слов: {с, ac, cb, acb, aac,..., aaa...acb...b, ...}. Обратите внимание что слова, в которых нет букв a или b, получаются за счет того, что результат итерации может не содержать символов, то есть быть пустым словом.
Последней операцией, которая используется в формулах, является сложение. Сложение соответствует объединению множеств. Так, обозначение (a+b)*c+d(ac*+) описывает множество всех последовательностей из букв a и b (обозначается (a+b)*), к концу которых присоединена буква c, объединенного с множеством слов, начинающихся с буквы d, за которой следует буква a, а за ней любое число букв c и ещё одним однобуквенным словом (d умножить на пустое слово — это d)."
Слева приведены примеры слов, которые удовлетворяют нашему условию, справа примеры слов, которые не удовлетворяют ему. Благодаря подсветке вы можете видеть, какие из этих примеров и контрпримеров удовлетворяют построенному вами выражению, а какие — нет.
В качестве начального решения вы можете видеть выражение, которому удовлетворяет слово Р и пустое слово.