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