Существует ли конечный автомат, реализующий суммирование двух двоичных чисел? (входное слово состоит из пар цифр слагаемых, начиная с конца, выходное - из пар цифр суммы, начиная с конца).
Я думаю, что нет. Предположим, есть входное слово

. В таком случае мы должны помнить единицу из предыдущего разряда, но если таких "переносов" будет больше, то нужно больше состояний. Но в любом случае мы не сможем выделить конечное число состояний. Прав ли я?