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

м
Откат правок 5.19.239.65 (обс.) к версии Oleg3280
м (Откат правок 5.19.239.65 (обс.) к версии Oleg3280)
{{Рамка}}
 
== КонченыйКонечный автомат ==
'''Конечный автомат''' (в [[w:теория алгоритмов|теории алгоритмов]]) — [[w:математика|математическая]] [[w:абстракция|абстракция]], позволяющая описывать пути изменения [[w:состояние|состояния]] объекта в зависимости от его текущего состояния и [[w:входные данные|входных данных]], при условии что общее возможное количество состояний [[w:конечное множество|конечно]]. Конечный автомат является частным случаем [[w:абстрактный автомат|абстрактного автомата]]. Конечный автомат может быть детерминированным или недетерминированным, в зависимости от того, имеется ли один или несколько вариантов его поведения на каком-то шаге.
 
 
{{Рамка}}
 
== Абстрактный автомат ==
'''Абстра́ктный автома́т''' (в [[w:теория алгоритмов|теории алгоритмов]]) — [[w:математика|математическая]] [[w:абстракция|абстракция]], [[w:модель|модель]] [[w:дискретное устройство|дискретного устройства]], имеющего один вход, один выход и в каждый момент времени находящегося в одном [[w:состояние|состоянии]] из множества возможных. На вход этому устройству поступают [[w:символ|символ]]ы одного [[w:язык|язык]]а, на выходе оно выдаёт символы (в общем случае) другого языка.
7086

правок