Материал взят из курса 6.01.
Автоматы
Автомат - это метод моделирования системы, вывод которой зависит от истории ввода.
Мы можем задать автомат указав:
- множество состояний, S
- множество вводов, I
- множество выводов, O
- функцию следующего состояния, \(n(i_t, s_t) \mapsto s_{t+1} \), для ввода и состояния в момент \(t \) задаёт состояние в момент \(t+1\)
- функцию вывода, \( o(i_t, s_t) \mapsto o_t \), для ввода и состояния в момент \(t\) задаёт вывод в момент \(t\); и
- начальное состояние, \(s_o\), состояние в момент времени 0.
Автомат задержки
Автомат берет ввод и отправляет его на вывод, но с задержкой на один шаг.
$$\begin{array}{ccc} S &=& anything\\ I &=& anything\\ O &=& anything\\ n(s, i) &=& i\\ o(s, i) &=& s\\ s_0 &=& 0\\ \end{array} $$Дана последовательность \(i_0, i_1, i_2, ..\), автомат будет выводить \(0, i_0, i_1, i_2, ..\).
Аккумулятор
Вывод из аккумулятора равен сумме всех вводов.
$$\begin{array}{ccc} S &=& numbers\\ I &=& numbers \\ O &=& numbers \\ n(s,i) &=& s + i\\ o(s, i) &=& n(s, i)\\ s_0 &=& 0 \end{array} $$| time | 0 | 1 | 2 | 3 |
| input | 100 | -3 | 4 | -123 |
| state | 0 | 100 | 97 | 101 |
| output | 100 | 97 | 101 | -22 |
Автомат принимающий язык
Рассмотрим автомат, вывод из него True, если вводимая строка удовлетворяет шаблону, False в противном случае. Пусть шаблон будет a, b, c, a, b, c, a, b, c, ... Автомат использует состояния 0, 1, 2, в которых он ожидает a, b, c соответственно, и он использует состояние 3 для случаев, когда он встретил не то, что ожидал. Когда автомат попадает в состояние 3, он ни когда его не покидает.
$$ \begin{array}{ccc} S &=& \{0, 1, 2, 3\}\\ I &=& \{a, b, c\} \\ O &=& \{True, False\}\\ s_0 &=& 0 \end{array} $$ $$ n(s,i) = \left\{ \begin{array}{ccc} 1, &if& s=0, i=a\\ 2, &if& s=1, i=b\\ 0, &if& s=2, i=c\\ 3, &&otherwise&\\ \end{array}\right. $$ $$ o(s, i) = \left\{ \begin{array}{ccc} False, &if& n(s,i)=3\\ True && otherwise\\ \end{array}\right. $$Диаграмм перехода состояний приведена на рисунке.
Автомат в Python
Зададим абстрактный класс SM, он будет родителем для остальных классов автоматов.
class SM:
def start(self):
self.state = self.startState
def step(self, inp):
(s, o) = self.getNextValues(self.state, inp)
self.state = s
return o
def transduce(self, inputs, verbose = False):
self.start()
return [self.step(inp) for inp in inputs]
Метод getNextValues берет состояние и ввод в момент t и возвращает состояние в момент t+1 и вывод в момент t. Метод step берет ввод, изменяет состояние автомата и возвращает вывод. Метод transduce для последовательности вводов возвращает выводы.
Автомат с задержкой
class Delay(SM):
def __init__(self, v0):
self.startState = v0
def getNextValues(self, state, inp):
return (inp, state)
Incrementor
Автомат Incrementor берёт ввод и возвращает его плюс константа incr.
class Increment(SM):
def __init__(self, incr):
self.incr = incr
def getNextState(self, state, inp):
return safeAdd(inp, self.incr)
Вспомогательная функция safeAdd, понадобится для соединения с задержкой.
def safeAdd(a, b):
if a == 'undefined' or b == 'undefined':
return 'undefined'
else:
return a + b