Машина Тьюринга: различия между версиями

{{Рамка}}

 

'''Конечный автомат''' (в [[w:теория алгоритмов|теории алгоритмов]]) — [[w:математика|математическая]] [[w:абстракция|абстракция]], позволяющая описывать пути изменения [[w:состояние|состояния]] объекта в зависимости от его текущего состояния и [[w:входные данные|входных данных]], при условии что общее возможное количество состояний [[w:конечное множество|конечно]]. Конечный автомат является частным случаем [[w:абстрактный автомат|абстрактного автомата]]. Конечный автомат может быть детерминированным или недетерминированным, в зависимости от того, имеется ли один или несколько вариантов его поведения на каком-то шаге.

 

 

{{Рамка}}

== Абстрактный автомат ==

'''Абстра́ктный автома́т''' (в [[w:теория алгоритмов|теории алгоритмов]]) — [[w:математика|математическая]] [[w:абстракция|абстракция]], [[w:модель|модель]] [[w:дискретное устройство|дискретного устройства]], имеющего один вход, один выход и в каждый момент времени находящегося в одном [[w:состояние|состоянии]] из множества возможных. На вход этому устройству поступают [[w:символ|символ]]ы одного [[w:язык|язык]]а, на выходе оно выдаёт символы (в общем случае) другого языка.