Машина состояний простыми словами

23 Август 2019 - Время чтения: 55 минуты

В программировании часто используется машина состояний, она же конечный автомат. Что это такое? Это распространённый принцип построения алгоритмов, который позволяет упростить их понимание и, соответственно, повысить их надёжность. Многие программы, от компиляторов языков программирования до компьютерных игр, представляют собой, по сути, машины состояний или их комбинацию. Давайте рассмотрим несколько примеров.

Самый простое, что мне приходит в голову - шагающий человек. Он сначала идёт левой ногой, потом правой. Значит, у нас будет два состояния. Или три, если ещё считать состояние -1, при котором происходит завершение программы.


Исходный код на C99
#include <stdio.h>
 
int main(void)
{
    for (int state = 0; state >= 0;) {
        switch (state) {
            case 0:
                printf("Left!\n");
                state = getchar() == '\n' ? 1 : -1;
                break;
            case 1:
                printf("Right!\n");
                state = getchar() == '\n' ? 0 : -1;
                break;
        }
    }
    return 0;
}

На первый взгляд программа выглядит слишком громоздкой и переусложнённой. Конечно, данную задачу можно было бы решить гораздо короче и проще.


Исходный код на C99
#include <stdio.h>
 
int main(void)
{
    for (int i = 0;; i ^= 1) {
        printf("%s!\n", i == 0 ? "Left" : "Right");
        if (getchar() != '\n') break;
    }
    return 0;
}

Зачем же расписывать подробно машину состояний? Дело в том, что далеко не все задачи так примитивны, и зачастую выделить в них несколько состояний - это самый понятный способ их решить. А вообще любую машину состояний можно переписать по-другому, в обычном стиле. В первом варианте кода видны все признаки классической машины состояний. Мы выделили несколько состояний, и в каждом из них принимаем решение, в какое состояние переключиться дальше.

Попробуем какой-нибудь пример хотя бы чуть-чуть поинтереснее. Чтобы состояний было как минимум три. Какой предмет или ситуация из жизни имеют три состояния? Не знаю, у кого как, а у меня это в первую очередь ассоциируется со светофором. У него ведь три состояния, правильно? Красный, жёлтый, зелёный. Давайте попробуем расписать подробно.

  1. Красный цвет. Дальше переключаемся в состояние 1 (жёлтый).
  2. Жёлтый цвет. Дальше переключаемся в состояние 2 (зелёный).
  3. Зелёный цвет. Дальше переключаемся в состояние 1 (жёлтый).

А вот теперь у нас жёлтый цвет, куда мы должны переключиться? Казалось бы, в красный, но мы же написали, что в состоянии 1 (жёлтый) переключаемся в состояние 2 (зелёный). Какой-то у нас получается неправильный светофор.


Исходный код на C99
#include <stdio.h>
 
int main(void)
{
    for (int state = 0; state >= 0;) {
        switch (state) {
            case 0:
                printf("Red\n");
                state = getchar() == '\n' ? 1 : -1;
            break;
            case 1:
                printf("Yellow\n");
                state = getchar() == '\n' ? 2 : -1;
            break;
            case 2:
                printf("Green\n");
                state = getchar() == '\n' ? 1 : -1;
            break;
        }
    }
    return 0;
}

Если запустить эту программу, то можно убедиться, что красный цвет у нас зажжётся только один раз, а потом программа будет переключаться из зелёного в жёлтый и обратно. Это совершенно непохоже на нормальную работу! Что же делать? Получается, что такую, казалось бы, простую вещь, как светофор, невозможно запрограммировать? С помощью машины с тремя состояниями - да, нельзя. Видимо, должно быть четыре состояния, потому что у нас две разновидности жёлтого цвета - тот, который после красного и перед зелёным, и тот, который после зелёного и перед красным. Или можно объяснить по-другому: состояниями являются не цвета, а переходы между ними, а вот их - четыре.

  1. Жёлтый→красный. Гасим жёлтую лампу, зажигаем красную и переходим в состояние 1.
  2. Красный→жёлтый. Гасим красную лампу, зажигаем жёлтую и переходим в состояние 2.
  3. Жёлтый→зелёный. Гасим жёлтую лампу, зажигаем зелёную и переходим в состояние 3.
  4. Зелёный→жёлтый. Гасим зелёную лампу, зажигаем жёлтую и переходим в состояние 0.

Так что у светофора не три, а четыре состояния. Для наглядности я написал скрипт, который рисует такой светофор.


Исходный код на JavaScript
window.onload = setInterval((function() {
    var canvas = document.getElementById("stoplight");
    var ctx = canvas.getContext("2d");
    var colors = {black: "#111111", red: "#FF4136", yellow: "#FFDC00", green: "#2ECC40"};
    var size = Math.min(canvas.width, canvas.height) / 5;
 
    var square = (function(x, y, size, color) {
        this.fillStyle = color;
        this.fillRect(x, y, size, size);
    });
 
    var circle = (function(x, y, r, color) {
        this.fillStyle = color;
        this.beginPath();
        this.arc(x, y, r, 0, 2 * Math.PI);
        this.fill();
    });
 
    var redOff = square.bind(ctx, (canvas.width - size) / 2, size, size, colors.black);
    var redOn = circle.bind(ctx, canvas.width / 2, canvas.height / 2 - size, size / 2, colors.red);
    var yellowOff = square.bind(ctx, (canvas.width - size) / 2, size * 2, size, colors.black);
    var yellowOn = circle.bind(ctx, canvas.width / 2, canvas.height / 2, size / 2, colors.yellow);
    var greenOff = square.bind(ctx, (canvas.width - size) / 2, size * 3, size, colors.black);
    var greenOn = circle.bind(ctx, canvas.width / 2, canvas.height / 2 + size, size / 2, colors.green);
 
    var state = 0;
 
    return (function () {
        switch (state) {
            case 0:
                redOff();
                yellowOff();
                greenOff();
                state = 1;
                break;
            case 1:
                redOn();
                state = 2;
                break;
            case 2:
                redOff();
                yellowOn();
                state = 3;
                break;
            case 3:
                yellowOff();
                greenOn();
                state = 4;
                break;
            case 4:
                greenOff();
                yellowOn();
                state = 5;
                break;
            case 5:
                yellowOff();
                redOn();
                state = 2;
                break;
        }
    });
}).call(this), 2000);

Как видите, там даже шесть состояний. Нулевое гасит все лампы, первое зажигает только красную, а дальше как было описано ранее. Давайте напоследок рассмотрим ещё какую-нибудь задачу, которая хорошо ложится на машину состояний.

Допустим, нам дана строка, и нужно проверить, что регистры букв соответствуют тем, что мы ожидаем в обычном слове. Другими словами, либо все буквы должны быть строчные (обычное слово), либо первая прописная, остальные строчные (имя собственное), или все прописные (аббревиатура). Любые другие варианты не разрешены.

Давайте сначала подумаем, как решить эту задачу без машины состояний. Наверное, мы бы сначала прочитали строку, а потом начали бы проверять все варианты. Уж поверьте, получится малопонятная и малоприятная мешанина кода.

Вместо этого я предлагаю выделить следующие состояния:

  1. Начало работы. Читаем символ, если это строчная буква - переходим в состояние 1. Если заглавная - в состояние 2. Если ни то, ни другое - в состояние -1 (ошибка).
  2. Прочитана одна буква, и это строчная. Значит, мы должны проверить, что и очередная тоже строчная, потому что заглавных букв после строчных быть не может. Если это не так - переходим в состояние -1, иначе остаёмся здесь.
  3. Прочитана одна заглавная буква. Ещё непонятно, то ли это имя собственное, то ли аббревиатура. Значит, читаем очередной символ, если это заглавная - переходим в состояние 3. А если строчная, в состояние 4? Нет, в состояние 1, потому что теперь все остальные буквы тоже должны быть строчными, а в состоянии 1 именно это и проверяется.
  4. Прочитаны две заглавные буквы, значит и дальше такие же. Если это не так - ошибка, иначе остаёмся здесь.

Исходный код C99
#include <ctype.h>
#include <stdio.h>
 
int main(void)
{
    int state = 0;
    for (int ch; (ch = getchar()) != EOF && ch != '\n';) {
        switch (state) {
            case 0:
                state = islower(ch) ? 1 : isupper(ch) ? 2 : -1;
                break;
            case 1:
                if (!islower(ch)) state = -1;
                break;
            case 2:
                state = isupper(ch) ? 3 : islower(ch) ? 1 : -1;
                break;
            case 3:
                if (!isupper(ch)) state = -1;
                break;
        }
    }
    printf("%s!\n", state < 0 ? "Error" : "Correct");
    return 0;
}

Обратите внимание - перейдя в состояние -1, мы из него уже никогда не выйдем, в свитче даже нет кейса для него. Действительно, если ошибка однажды возникла, то и вся оставшаяся строка неправильная. Впрочем, можно в состоянии -1 сразу выходить из цикла. Это зависит от специфики задачи. Если бы это была функция, которая проверяет строку, то логично было бы сразу возвратить ошибку, а не проверять остаток строки до конца. Или можно вообще запретить ввод "неправильных" символов. Чуть ниже есть форма ввода, она работает именно так. Можете проверить и убедиться!


Исходный код на JavaScript
(function() {
    var isdelkey = function(key) { return key === 8 || key === 46; };
    var islower = function(ch) { return 96 < ch && ch < 123; };
    var isupper = function(ch) { return 64 < ch && ch < 91; };
 
    var state = 0;
 
    this.onkeydown = (function(event) {
        if (isdelkey(event.keyCode)) {
            state = 0;
            this.value = "";
            return false;
        }
    });
 
    this.onkeypress = (function(event) {
        var ch = event.charCode;
 
        switch (state) {
            case 0:
                if (islower(ch)) {
                    state = 1;
                } else if (isupper(ch)) {
                    state = 2;
                } else {
                    return false;
                }
            break;
            case 1:
                if (!islower(ch)) return false;
            break;
            case 2:
                if (isupper(ch)) {
                    state = 3;
                } else if (islower(ch)) {
                    state = 1;
                } else {
                    return false;
                }
            break;
            case 3:
                if (!isupper(ch)) return false;
            break;
        }
    });
}).call(document.getElementById("word"));

Какие ещё задачи, по-вашему, удобно решать с помощью машины состояний? А может, есть такие, которые с их помощью, как вам кажется, решить невозможно? Или вы хотели бы решить, но не знаете, как? Пишите комментарии!

Currently there are no comments, so be the first!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории