Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Припишем каждому, стоящему в очереди, «1» или «0», в зависимости от того, голосует .он «за» или «против». Известно, что рядом с каждым человеком (непосредственно впереди его в очереди или сзади) есть человек, голосующий «за». Постройте конечный автомат, распознающий все такие наборы из «0» и «1» или докажите, что это невозможно
Автомат должен распознавать такие последовательности, в которых нет трёх нулей, стоящих рядом, и единиц, стоящих по одной. Длинная последовательность единиц будет крутиться на S1. Если при старте выдаётся 0, мы идём в S2 и проверяем следующий символ. Если там ноль, то программа переходит в S6, и проверяет, будет ли с этим нулём единица. Если нет, то переходит в S5, что делает невозможным переход в конечное состояние, если единица - отправляем в S3, давая "шанс". Если в S3 мы получаем 0, то одна единица стоит без пары, а такая последовательность считываться не должна и программа отправляется в S5, иначе в S1.