2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Существует ли конечный автомат
Сообщение30.03.2014, 19:37 
Аватара пользователя
MestnyBomzh в сообщении #843220 писал(а):
но если таких "переносов" будет больше, то нужно больше состояний.
Почему? Вроде пока только 2 состояния - есть перенос или нет.

 
 
 
 Re: Существует ли конечный автомат
Сообщение30.03.2014, 19:50 
MestnyBomzh в сообщении #843220 писал(а):
Существует ли конечный автомат, реализующий суммирование двух двоичных чисел? (входное слово состоит из пар цифр слагаемых, начиная с конца, выходное - из пар цифр суммы, начиная с конца).
а что Вы вообще понимаете под "выходным" словом? у нас же конечный автомат, у него только "входные" бывают :-)

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

 
 
 
 Re: Существует ли конечный автомат
Сообщение30.03.2014, 21:32 
Существует и для любой произвольной длины. Достаточно знать был ли перенос в предыдущем разряде или нет.

 
 
 
 Re: Существует ли конечный автомат
Сообщение30.03.2014, 22:17 
Аватара пользователя
Изображение Вот, вроде написал, так верно будет?
Начало, ес-сно в $q_0$

 
 
 
 Re: Существует ли конечный автомат
Сообщение31.03.2014, 08:12 
Мне на матрице проще проверить было бы. Можем попробовать сравнить матрицы переходов.

 
 
 
 Re: Существует ли конечный автомат
Сообщение31.03.2014, 15:07 
Аватара пользователя
Изображение
Если таблицей удобней, то вот так, или вы про что-то другое?

 
 
 
 Re: Существует ли конечный автомат
Сообщение31.03.2014, 20:26 
Аватара пользователя
 ! 
lampard в сообщении #843721 писал(а):
:|

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

 
 
 
 Re: Существует ли конечный автомат
Сообщение31.03.2014, 23:20 
MestnyBomzh
Тут ваша задача есть http://www.intuit.ru/studies/courses/10 ... 310?page=1

 
 
 
 Re: Существует ли конечный автомат
Сообщение01.04.2014, 08:38 
Аватара пользователя
Lukum
За ссылку спасибо, но странно, что там считывается по два символа, а должно же по-одному

 
 
 
 Re: Существует ли конечный автомат
Сообщение01.04.2014, 08:51 
Аватара пользователя
 i  MestnyBomzh, таблицы тоже следует оформлять $\TeX$ом

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group