Материал взят из курса 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