Существует ли конечный автомат

[MestnyBomzh]

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

[Xaositect]

MestnyBomzh в сообщении #843220 писал(а):

но если таких "переносов" будет больше, то нужно больше состояний.

Почему? Вроде пока только 2 состояния - есть перенос или нет.

[patzer2097]

MestnyBomzh в сообщении #843220 писал(а):

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

а что Вы вообще понимаете под "выходным" словом? у нас же конечный автомат, у него только "входные" бывают

[Xaositect]

Имеется в виду конечный преобразователь (он же конечный автомат Мили https://ru.wikipedia.org/wiki/%D0%90%D0 ... 0%BB%D0%B8)

[Lukum]

Существует и для любой произвольной длины. Достаточно знать был ли перенос в предыдущем разряде или нет.

[MestnyBomzh]

Вот, вроде написал, так верно будет?
Начало, ес-сно в $q_0$

[Lukum]

Мне на матрице проще проверить было бы. Можем попробовать сравнить матрицы переходов.

[MestnyBomzh]

Если таблицей удобней, то вот так, или вы про что-то другое?

[Deggial]

lampard в сообщении #843721 писал(а):

:|

lampard заблокирован на две недели за серию бессодержательных сообщений. Сообщения будут удалены.

[Lukum]

MestnyBomzh
Тут ваша задача есть http://www.intuit.ru/studies/courses/10 ... 310?page=1

[MestnyBomzh]

Lukum
За ссылку спасибо, но странно, что там считывается по два символа, а должно же по-одному

[Deggial]

MestnyBomzh, таблицы тоже следует оформлять $\TeX$ом