Описание тега fsm

Конечный автомат, конечный автомат или конечный автомат используется в информатике или теории логики для представления конечного числа состояний и переходов между состояниями.

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

Пример реализации конечного автомата в псевдокоде, принимающего все десятичные целые числа:

state = 0;
digits = "152341264"; // Some sequence of decimal digits
for (k = 0; k < len(digits); k++) {
    switch (state) {
    case 0: // Initial state
        if (digits[k] is a decimal digit)
            state = 1;
        else
            state = 2;
        break;
    case 1: // Digit found, also an accepting state
        if (digits[k] is a decimal digit)
            state = 1;
        else
            state = 2;
        break;
    case 2: // Dead state
        break;
    }
}
FSM accepts the string digits if it finishes at state 1.

Конечные автоматы представляют все обычные языки или языки Типа 3, которые являются самыми низкими в иерархии Хомского, ниже контекстно-свободных (Тип 2) языков, которые ниже контекстно-зависимых языков (Тип 1), которые находятся ниже перечислимый (тип 0) языков.

Страница Википедии

Тег также известен как конечный автомат в stackru.