Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Рыцари, которые говорят только правду, и лжецы, которые всегда лгут, выстроились в ряд. (В ряду хотя бы один человек). Каждый из них произнёс фразу «Все мои соседи лжецы». Обозначим рыцаря буквой Р, а лжеца — буквой Л. Тогда каждой последовательности рыцарей и лжецов, для которой выполняется условие задачи, соответствует некоторое слово.
Постройте схему, которая будет распознавать слова в алфавите {Л, Р}, соответствующие описанным в задаче последовательностям рыцарей и лжецов.
Данная схема состоит из вершин (называемых состояниями) и стрелок. Каждая стрелка соединяет два состояния и символизирует переход схемы из первого состояния во второе.. Схема начинает работу в начальном состоянии S0, выделенном оранжевым. Поступающее на вход слово анализируется посимвольно. При анализе каждого символа схема переходит из текущего состояния по стрелке, над которой написан этот символ.
После того, как всё слово проанализировано, схема заканчивает работу в одном из состояний. Некоторые состояния необходимо пометить как конечные (жирная каёмка, для пометки кликните на вершину). Это те состояния, в которых схема оказывается, в случае, если поступившее на вход схемы слово соответствует условию.
Если первый лжец, то следующий обязательно рыцарь и мы попали в состояние S2. Если какой-то символ был Р, то, если автомат до этого момента прочитал, то мы обязательно оказались в состоянии S2, т.к. только сюда входят стрелки с Р. Далее может идти только Л, и если дальше идет Р, то мы снова вернулись в то жде состояние, а если после Л идет Л, то третьей Л быть не может, тогда дальше идет Р и мы снова вернулись в состояние S2. Если какая-то последовательность проходит по этому автомату, то здесь нет трех Л подряд и нет двух Р подряд, этого достаточно для того, чтобы условие выполнялось, за исключением случаев, когда две крайних буквы лжецы, первые две не могут быть, мы это разобрали в начале, а чтобы последние две буквы не были Л, состояние S1 не может быть конечным.