2015-05-30
1111
Автомат может быть задан с помощью автоматной ленты или ленты Тьюринга (табл. 4.6).
Таблица 4.6 – Автоматная лента Тьюринга
| Такт | ||||||||||
| Входной сигнал | х 1 | х 4 | - | х 2 | х 4 | - | х 3 | х 4 | - | |
| Состояние | а 1 | а 2 | а 5 | а 1 | а 3 | а 6 | а 1 | а 4 | а 7 | а 1 |
| Выходной сигнал | - | y 1 | - | - | y 2 | - | - | y 3 | - |
Таблица 4.6 построена по табл. 4.1 и табл. 4.2 автомата Мили и содержит 4 строки – номер такта, входной сигнал, состояние и выходной сигнал. Особенность такой ленты состоит в том, что для любой пары соседних тактов t и t +1 можно выделить четверку символов (выделена жирной линей в табл. 4.6), которая показывает в какое состояние перейдет цифровой автомат в такте t +1 и какой выходной сигнал будет сформирован под действием входного сигнала.
Тьюринг (английский ученый, занимавшийся исследованиями конечных автоматов) показал, что любому конечному автомату соответствует эквивалентная ему машина Тьюринга, функционирование которой можно задавать лентой Тьюринга.
