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