как проектируются микросхемы
Как проектируют микросхемы - ЯПлакалъ
Микросхемы пишут на языке Verilog. Примерно как программы для компов пишут на языках программирования C++ и прочих, так и процессоры для ...
finite state machine
Исходный код на верилоге будущей микрухи долго отлаживается виртуально. Пишутся тесты, которые подают виртуальные сигналы на входы, просматриваются внутренние и выходные сигналы, прохождение данных, переходы по состояниям внутренних конечных автоматов (fsm - <anchor>finite state machine</anchor>), и подобное.
Конечный автомат — Википедия
Конечный автомат — Википедия

# Конечный автомат

Материал из Википедии — свободной энциклопедии

Текущая версия страницы пока [не проверялась](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D1%81%D1%82%D0%B0%D1%82%D0%B5%D0%B9/%D0%9F%D0%BE%D1%8F%D1%81%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B4%D0%BB%D1%8F_%D1%87%D0%B8%D1%82%D0%B0%D1%82%D0%B5%D0%BB%D0%B5%D0%B9 "Википедия:Проверка статей/Пояснение для читателей") опытными участниками и может значительно отличаться от [версии, проверенной 27 августа 2022 года](https://ru.wikipedia.org/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&stable=1); проверки требуют [18 правок](https://ru.wikipedia.org/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&oldid=125118843&diff=cur&diffonly=0).

[Перейти к навигации](#mw-head) [Перейти к поиску](#searchInput)

[![](//upload.wikimedia.org/wikipedia/ru/thumb/c/c0/%D0%90%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82.jpg/220px-%D0%90%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82.jpg)](/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:%D0%90%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82.jpg) Упрощённая схема абстрактного автомата.

x{\\displaystyle x}![{\displaystyle x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4) — входная буква, принадлежащая множеству входного алфавита X{\\displaystyle X}![{\displaystyle X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)

y{\\displaystyle y}![{\displaystyle y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d) — выходная буква, принадлежащая множеству выходного алфавита Y{\\displaystyle Y}![{\displaystyle Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/961d67d6b454b4df2301ac571808a3538b3a6d3f)

s{\\displaystyle s}![{\displaystyle s}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632) — внутреннее состояние, одно из множества внутренних состояний S{\\displaystyle S}![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)

**Коне́чный автома́т** (КА) в [теории алгоритмов](/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2 "Теория алгоритмов") — [математическая абстракция](/wiki/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B0%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%86%D0%B8%D1%8F "Математическая абстракция"), [модель](/wiki/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C "Модель") [дискретного устройства](/w/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B5_%D1%83%D1%81%D1%82%D1%80%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%BE&action=edit&redlink=1 "Дискретное устройство (страница отсутствует)"), имеющего один вход, один выход и в каждый момент времени находящегося в одном [состоянии](/wiki/%D0%A1%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) "Состояние (информатика)") из множества возможных. Является частным случаем [абстрактного дискретного автомата](/wiki/%D0%90%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Абстрактный автомат"), число возможных внутренних состояний которого _[конечно](/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE "Конечное множество")_.

При работе на вход КА последовательно поступают входные воздействия, а на выходе КА формирует выходные сигналы. Обычно под входными воздействиями принимают подачу на вход автомата [символов](/wiki/%D0%A1%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB "Символ") одного [алфавита](/wiki/%D0%90%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) "Алфавит (информатика)"), а на выход КА в процессе работы выдаёт символы в общем случае другого, возможно даже не пересекающегося со входным, алфавита.

Помимо конечных автоматов существуют и бесконечные дискретные автоматы — автоматы с бесконечным числом внутренних состояний.

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

Различают [детерминированные КА](/wiki/%D0%94%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Детерминированный конечный автомат") — автоматы, в которых следующее состояние однозначно определяется текущим состоянием и входным символом и выход зависит только от текущего состояния и текущего входа, и [недетерминированные КА](/wiki/%D0%9D%D0%B5%D0%B4%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Недетерминированный конечный автомат"), следующее состояние у которых в общем случае не определено и, соответственно, не определён выходной сигнал. Если переход в последующие состояния происходит с некоторыми вероятностями, то такой КА называют [_вероятностным_ КА](/wiki/%D0%92%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Вероятностный автомат").

Примерами физической реализации КА могут служить любые цифровые системы, например, компьютеры или некоторые логические узлы компьютеров с памятью — [триггеры](/wiki/%D0%A2%D1%80%D0%B8%D0%B3%D0%B3%D0%B5%D1%80 "Триггер") и другие устройства. Комбинационная последовательная логика не может являться КА, так как не имеет внутренних состояний (не имеет памяти).

С абстрактной точки зрения КА изучается разделом [дискретной математики](/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 "Дискретная математика") — _теория конечных автоматов_.

[Теория конечных автоматов](/w/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D1%85_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%BE%D0%B2&action=edit&redlink=1 "Теория конечных автоматов (страница отсутствует)") практически широко используется, например, в [синтаксических](/wiki/%D0%A1%D0%B8%D0%BD%D1%82%D0%B0%D0%BA%D1%81%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%82%D0%BE%D1%80 "Синтаксический анализатор") и [лексических анализаторах](/wiki/%D0%9B%D0%B5%D0%BA%D1%81%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%82%D0%BE%D1%80 "Лексический анализатор"), [тестировании программного обеспечения](/wiki/%D0%A2%D0%B5%D1%81%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BE%D0%B1%D0%B5%D1%81%D0%BF%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F "Тестирование программного обеспечения") [на основе моделей](/wiki/%D0%A2%D0%B5%D1%81%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B0_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8 "Тестирование на основе модели").

## Содержание

- [1Формальное описание конечного автомата](#Формальное_описание_конечного_автомата)
  - [1.1Общее формальное описание](#Общее_формальное_описание)
  - [1.2Общее описание](#Общее_описание)
  - [1.3Другие способы задания функционирования КА](#Другие_способы_задания_функционирования_КА)
- [2Детерминированность](#Детерминированность)
- [3Автоматы и регулярные языки](#Автоматы_и_регулярные_языки)
- [4Минимизация автоматов](#Минимизация_автоматов)
- [5Специализированные языки программирования](#Специализированные_языки_программирования)
- [6Разработка моделей с использованием конечных автоматов](#Разработка_моделей_с_использованием_конечных_автоматов)
- [7Что может «делать» конечный автомат и последовательностная машина?](#Что_может_«делать»_конечный_автомат_и_последовательностная_машина?)
- [8См. также](#См._также)
- [9Примечания](#Примечания)
- [10Литература](#Литература)
- [11Ссылки](#Ссылки)

## Формальное описание конечного автомата

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=1 "Редактировать раздел «Формальное описание конечного автомата»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=1 "Редактировать код раздела «Формальное описание конечного автомата»")\]

[![](//upload.wikimedia.org/wikipedia/ru/thumb/3/31/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0_%D0%B0%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0.jpg/250px-%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0_%D0%B0%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0.jpg)](/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0_%D0%B0%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0.jpg) Обобщённая функциональная схема абстрактного автомата. «Память» — это совокупность внутренних состояний.

s(t){\\displaystyle s(t)}![{\displaystyle s(t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c484de351ba40ccb9a5ad522c29c1aac5686c0df) — текущее состояние;

s(t+1){\\displaystyle s(t+1)}![{\displaystyle s(t+1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/012c1628f38f77defa5b7b68fa0a35f149ce421e) — следующее состояние.

### Общее формальное описание

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=2 "Редактировать раздел «Общее формальное описание»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=2 "Редактировать код раздела «Общее формальное описание»")\]

Формально КА определяется в виде упорядоченной пятёрки элементов некоторых множеств:

A=(S,X,Y,δ,λ),{\\displaystyle A=(S,X,Y,\\delta ,\\lambda ),}![{\displaystyle A=(S,X,Y,\delta ,\lambda ),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7371ede80fa412496ed481e4b500be8e3ed7c80d)где S{\\displaystyle S}![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2) — конечное множество [состояний](/wiki/%D0%A1%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5 "Состояние") автомата;X,Y{\\displaystyle X,Y}![{\displaystyle X,Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8705438171d938b7f59cd1bfa5b7d99b6afa5cd) — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом;δ:S×X→S{\\displaystyle \\delta :S\\times X\\rightarrow S}![{\displaystyle \delta :S\times X\rightarrow S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8fb0acca209f2c02c084c7ce62cbfe66b561b151) — функция переходов;λ:S×X→Y{\\displaystyle \\lambda :S\\times X\\rightarrow Y}![{\displaystyle \lambda :S\times X\rightarrow Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52f5fbf505c205d36d229e8c11441df0d3738fb8) — функция выходов.

Абстрактный автомат с некоторым выделенным [состоянием](/wiki/%D0%A1%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5 "Состояние")s0{\\displaystyle s\_{0}}![{\displaystyle s_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25c32f35eb134d23b3c45f1c878d59b0a112ede4) (это состояние называют _начальным состоянием_) называется _инициальным автоматом_. Так как каждый КА имеет конечное число состояний, и любое из его состояний может быть назначено начальным состоянием, одному и тому же автомату соответствует N{\\displaystyle N}![{\displaystyle N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3) инициальных автоматов, N{\\displaystyle N}![{\displaystyle N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3) — число внутренних состояний КА. Таким образом, абстрактный КА определяет семейство инициальных автоматов. Если не указано начальное состояние, то поведение автомата всегда недетерминировано, выходное слово автомата зависит от начального состояния, поэтому полное детерминированное описание автомата будет[\[1\]](#cite_note-Кузнецов-1):

A=(S,X,Y,δ,λ,s0).{\\displaystyle A=(S,X,Y,\\delta ,\\lambda ,s\_{0}).}![{\displaystyle A=(S,X,Y,\delta ,\lambda ,s_{0}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6ca3cebbb51a5e6c3d0ea82d3621b9e84c4a84e)

Различают два класса КА: [автоматы Мура](/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82_%D0%9C%D1%83%D1%80%D0%B0 "Автомат Мура") — КА, у которых выходной сигнал зависит только от внутреннего состояния, по рисунку у автомата Мура нет связи от входа x(t){\\displaystyle x(t)}![{\displaystyle x(t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d54c275db3a1e620737b58e143b0818107fa5f5c) к функции выхода λ{\\displaystyle \\lambda }![{\displaystyle \lambda }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a), и [автоматы Мили](/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82_%D0%9C%D0%B8%D0%BB%D0%B8 "Автомат Мили") — выходной сигнал зависит как от внутреннего состояния, так и от состояния входа.

### Общее описание

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=3 "Редактировать раздел «Общее описание»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=3 "Редактировать код раздела «Общее описание»")\]

Существуют различные способы задания алгоритма функционирования конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятёрки элементов некоторых [множеств](/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) "Множество (математика)"):

M=(V,Q,q0,F,δ),{\\displaystyle M=(V,Q,q\_{0},F,\\delta ),}![{\displaystyle M=(V,Q,q_{0},F,\delta ),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69e064865d540eddd25877cb095deb38f99aa20f)где V{\\displaystyle V}![{\displaystyle V}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845) — _входной алфавит_ (конечное множество _входных символов_), из которого формируются _входные слова_, воспринимаемые конечным автоматом;Q{\\displaystyle Q}![{\displaystyle Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed) — _множество внутренних состояний_;q0{\\displaystyle q\_{0}}![{\displaystyle q_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d68d37de188ac61f0c0e3f31d5322d1c486f2f4) — _начальное состояние_(q0∈Q){\\displaystyle (q\_{0}\\in Q)}![{\displaystyle (q_{0}\in Q)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e1b5728ce16eef75b228c3da521cb53a679996b);F{\\displaystyle F}![{\displaystyle F}](https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57) — множество _заключительных, или конечных состояний_(F⊂Q){\\displaystyle (F\\subset Q)}![{\displaystyle (F\subset Q)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cbe68f338aae6b79f313d8b443fbe77ca5ad9e0);δ{\\displaystyle \\delta }![{\displaystyle \delta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5321cfa797202b3e1f8620663ff43c4660ea03a) — _функция переходов_, определённая как отображение δ:Q×(V∪{ε})→Q{\\displaystyle \\delta \\colon Q\\times (V\\cup \\{\\varepsilon \\})\\rightarrow Q}![{\displaystyle \delta \colon Q\times (V\cup \{\varepsilon \})\rightarrow Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc2dd5df44a3286574734933938416264a104ae2), такое, что δ(q,a)={r:q→ar}{\\displaystyle \\delta (q,a)=\\{r\\colon q\\,\\,{\\underset {a}{\\to }}\\,\\,r\\}}![{\displaystyle \delta (q,a)=\{r\colon q\,\,{\underset {a}{\to }}\,\,r\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6303c76a807b37cf557737e805318aa0d735e424), то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка символов) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке символов, обычно обозначаемой буквой ε.{\\displaystyle \\varepsilon .}![{\displaystyle \varepsilon .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5807913813d5188ce49b63a9b26d43f7a7763c19)

При анализе КА принято полагать, что конечный автомат начинает работу в некотором начальном состоянии q0{\\displaystyle q\_{0}}![{\displaystyle q_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d68d37de188ac61f0c0e3f31d5322d1c486f2f4), последовательно получает по одному символу из входного слова (цепочки входных символов). Считанный символ может перевести автомат в новое состояние или не перевести в новое состояние в соответствии с функцией переходов.

Получая входную цепочку символов x{\\displaystyle x}![{\displaystyle x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4) и делая переходы из состояния в состояние, автомат после получения последнего символа\[ _[прояснить](/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:%D0%9F%D1%80%D0%BE%D1%8F%D1%81%D0%BD%D0%B8%D1%82%D1%8C "Шаблон:Прояснить")_\] входного слова окажется в некотором состоянии q′{\\displaystyle q'}![{\displaystyle q'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/912405e5d416048908ea7978929975843d2ee4e6).

Если это состояние является заключительным, то говорят, что автомат допустил слово x{\\displaystyle x}![{\displaystyle x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)\[ _[прояснить](/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:%D0%9F%D1%80%D0%BE%D1%8F%D1%81%D0%BD%D0%B8%D1%82%D1%8C "Шаблон:Прояснить")_\]

### Другие способы задания функционирования КА

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=4 "Редактировать раздел «Другие способы задания функционирования КА»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=4 "Редактировать код раздела «Другие способы задания функционирования КА»")\]

Исходное

состояние
Следующее состояние
Входной

символ a
Входной

символ b
Любой

другой

символ
p0
p1
p0
p0
p1
p1
p2
p1
p2
p3
p4
p2
p3
p3
p5
p3
p4
p4
p4
p4
p5
p3
p5
p5

1. **[Диаграмма состояний](/wiki/%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%9C%D1%83%D1%80%D0%B0 "Диаграмма Мура")** (или иногда **граф переходов**) — графическое представление множества состояний и функции переходов. Представляет собой размеченный ориентированный [граф](/wiki/%D0%93%D1%80%D0%B0%D1%84_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) "Граф (математика)"), вершины которого — состояния КА, дуги — переходы из одного состояния в другое, а _метки дуг_ — символы, по которым осуществляется переход из одного состояния в другое. Если переход из состояния _q1_ в _q2_ может быть осуществлён по одному из _нескольких_ символов, то все они должны быть надписаны над дугой диаграммы.
2. **Таблица переходов** — табличное представление функции _δ_. Обычно в такой таблице каждой строке соответствует одно состояние (исходное и результатное), а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается результатное состояние, в которое должен перейти автомат, если в данном исходном состоянии он считал данный входной символ. Пример таблицы переходов для автомата, заданного в виде графа на рисунке 1, приведён справа.

## Детерминированность

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=5 "Редактировать раздел «Детерминированность»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=5 "Редактировать код раздела «Детерминированность»")\]

[![](//upload.wikimedia.org/wikipedia/commons/thumb/1/1f/%D0%93%D1%80%D0%B0%D1%84_%D0%BF%D0%B5%D1%80%D0%B5%D1%85%D0%BE%D0%B4%D0%BE%D0%B2_%D0%94%D0%9A%D0%90.svg/220px-%D0%93%D1%80%D0%B0%D1%84_%D0%BF%D0%B5%D1%80%D0%B5%D1%85%D0%BE%D0%B4%D0%BE%D0%B2_%D0%94%D0%9A%D0%90.svg.png)](/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:%D0%93%D1%80%D0%B0%D1%84_%D0%BF%D0%B5%D1%80%D0%B5%D1%85%D0%BE%D0%B4%D0%BE%D0%B2_%D0%94%D0%9A%D0%90.svg) Рисунок 1\. Пример графа переходов детерминированного КА.[![](//upload.wikimedia.org/wikipedia/commons/thumb/3/36/%D0%93%D1%80%D0%B0%D1%84_%D0%BF%D0%B5%D1%80%D0%B5%D1%85%D0%BE%D0%B4%D0%BE%D0%B2_%D0%9D%D0%94%D0%9A%D0%90-ru.svg/220px-%D0%93%D1%80%D0%B0%D1%84_%D0%BF%D0%B5%D1%80%D0%B5%D1%85%D0%BE%D0%B4%D0%BE%D0%B2_%D0%9D%D0%94%D0%9A%D0%90-ru.svg.png)](/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:%D0%93%D1%80%D0%B0%D1%84_%D0%BF%D0%B5%D1%80%D0%B5%D1%85%D0%BE%D0%B4%D0%BE%D0%B2_%D0%9D%D0%94%D0%9A%D0%90-ru.svg) Рисунок 2\. Пример графа переходов недетерминированного КА с самопроизвольными переходами[![](//upload.wikimedia.org/wikipedia/commons/thumb/f/f4/%D0%9D%D0%9A%D0%90_%D0%B1%D0%B5%D0%B7_e.svg/220px-%D0%9D%D0%9A%D0%90_%D0%B1%D0%B5%D0%B7_e.svg.png)](/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:%D0%9D%D0%9A%D0%90_%D0%B1%D0%B5%D0%B7_e.svg) Рисунок 3\. Недетерминированный КА с переходами из одного состояния в разные состояния при одинаковом входном воздействии

Конечные автоматы подразделяются на [детерминированные](/wiki/%D0%94%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Детерминированный конечный автомат") и [недетерминированные](/wiki/%D0%9D%D0%B5%D0%B4%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Недетерминированный конечный автомат").

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

Если рассмотреть случай, когда автомат формально задан следующим образом: M=(V,Q,S,F,δ){\\displaystyle M=(V,Q,S,F,\\delta )}![{\displaystyle M=(V,Q,S,F,\delta )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d396b071c68240cee89608c89538f8c34d9d4a9d), где S{\\displaystyle S}![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2) — множество _начальных состояний_ автомата, такое, что S⊆Q{\\displaystyle S\\subseteq Q}![{\displaystyle S\subseteq Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/523b28ba82e9c5119d91258dcf93450cceeca7ab), то появляется третий признак недетерминированности — наличие нескольких начальных (стартовых) состояний у автомата M{\\displaystyle M}![{\displaystyle M}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd).

_Теорема о детерминизации_\[ _[источник не указан 1553 дня](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%81%D1%8B%D0%BB%D0%BA%D0%B8_%D0%BD%D0%B0_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8 "Википедия:Ссылки на источники")_\] утверждает, что для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат (два конечных автомата называют эквивалентными, если их языки совпадают\[ _[прояснить](/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:%D0%9F%D1%80%D0%BE%D1%8F%D1%81%D0%BD%D0%B8%D1%82%D1%8C "Шаблон:Прояснить")_\]). Однако поскольку количество состояний в эквивалентном ДКА в худшем случае растёт [экспоненциально](/wiki/%D0%AD%D0%BA%D1%81%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%80%D0%BE%D1%81%D1%82 "Экспоненциальный рост") с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, [конечные автоматы с выходом](/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82_%D1%81_%D0%B2%D1%8B%D1%85%D0%BE%D0%B4%D0%BE%D0%BC "Конечный автомат с выходом") в общем случае не поддаются детерминизации.

В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА\[ _[источник не указан 1553 дня](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%81%D1%8B%D0%BB%D0%BA%D0%B8_%D0%BD%D0%B0_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8 "Википедия:Ссылки на источники")_\].

## Автоматы и регулярные языки

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=6 "Редактировать раздел «Автоматы и регулярные языки»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=6 "Редактировать код раздела «Автоматы и регулярные языки»")\]

Для конечного автомата можно определить язык (множество слов) в алфавите V{\\displaystyle V}![{\displaystyle V}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845), который он **допускает**, — так называются слова, чтение которых переводит автомат из начального состояния в одно из заключительных состояний.

[Теорема Клини](/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%BB%D0%B8%D0%BD%D0%B8 "Теорема Клини") утверждает, что язык является [регулярным](/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA "Регулярный язык") тогда и только тогда, когда он допускается некоторым конечным автоматом, используемым в этом языке.

## Минимизация автоматов

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=7 "Редактировать раздел «Минимизация автоматов»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=7 "Редактировать код раздела «Минимизация автоматов»")\]

Основная статья: **[Минимизация ДКА](/wiki/%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%94%D0%9A%D0%90 "Минимизация ДКА")**

Для любого регулярного языка существует единственный с точностью до [изоморфизма](/wiki/%D0%98%D0%B7%D0%BE%D0%BC%D0%BE%D1%80%D1%84%D0%B8%D0%B7%D0%BC "Изоморфизм") автомат, принимающий этот язык и обладающий при этом наименьшим возможным числом состояний. Минимальный автомат для языка, заданного детерминированным конечным автоматом, может быть осуществлён за полиномиальное время, что позволяет оптимизировать расход памяти, требуемый для работы с автоматом, а также решать такие задачи, как проверка эквивалентности двух автоматов за полиномиальное время.

## Специализированные языки программирования

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=8 "Редактировать раздел «Специализированные языки программирования»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=8 "Редактировать код раздела «Специализированные языки программирования»")\]

- Язык последовательных функциональных схем [SFC](/wiki/SFC "SFC") (Sequential Function Chart) — [графический язык программирования](/wiki/%D0%93%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F "Графический язык программирования"), широко используется для программирования промышленных логических контроллеров ( [ПЛК](/wiki/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D1%83%D0%B5%D0%BC%D1%8B%D0%B9_%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BE%D0%BD%D1%82%D1%80%D0%BE%D0%BB%D0%BB%D0%B5%D1%80 "Программируемый логический контроллер")).

В графическом языке SFC программа описывается в виде схематической последовательности шагов, объединённых переходами.

## Разработка моделей с использованием конечных автоматов

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=9 "Редактировать раздел «Разработка моделей с использованием конечных автоматов»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=9 "Редактировать код раздела «Разработка моделей с использованием конечных автоматов»")\]

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

## Что может «делать» конечный автомат и последовательностная машина?

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=10 "Редактировать раздел «Что может «делать» конечный автомат и последовательностная машина?»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=10 "Редактировать код раздела «Что может «делать» конечный автомат и последовательностная машина?»")\]

Ответ даётся в различных терминах в зависимости от того, является ли автомат (соответственно П-машина) автономным или нет[\[2\]](#cite_note-2). Автономный конечный автомат, начиная с некоторого такта, может лишь генерировать периодическую последовательность состояний **х** (соответственно П-машина — последовательность выходных символов **y**). Если эта последовательность состоит лишь из одного символа, то это означает, что за конечное число тактов автомат достигает равновесного состояния. Если же эта последовательность содержит несколько символов, это означает, что автомат последовательно проходит состояния, соответствующие этим символам, а затем работа автомата неограниченно долго периодически повторяется. Более того, какова бы ни была периодическая последовательность состояний конечной длины, всегда может быть построен автономный конечный автомат, который, начиная уже со второго такта, генерирует эту последовательность. Ничего иного, кроме периодического повторения одного и того же состояния или конечной последовательности состояний, автономный автомат «делать» не может. Однако в связи с тем, что последовательное выполнение заданного цикла операций типично для многих областей современной техники, динамические системы, которые в приемлемой идеализации можно рассматривать как автономный автомат, имеют широкое применение.

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

Современным примером служат многие станки-автоматы, автоматические линии и системы автоматического управления циклическими производствами. Если автомат не автономен, то есть состояние входа изменяется от такта к такту, то ответ на вопрос, что может «делать» и что не может «делать» конечный автомат, можно дать в разных терминах. Например, ответ можно сформулировать на языке представления событий. Действительно, неавтономный конечный автомат или последовательностная машина лишь преобразуют входные последовательности символов в последовательности состояний или выходных символов, и сказать, что может и что не может «делать» конечный автомат, значит выяснить, какие преобразования последовательностей возможны в конечном автомате, а какие невозможны. Но так как количество состояний (соответственно выходных символов) конечно, этот вопрос эквивалентен такому вопросу: при каких входных последовательностях возникает каждое из возможных состояний (или каждый из выходных символов). Этот последний вопрос в терминах, принятых в теории конечных автоматов, формулируется так: какие события могут и какие не могут быть представлены в конечном автомате каждым из возможных состояний (или каждым из выходных символов).

Ответ даётся [теоремами Клини](/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%BB%D0%B8%D0%BD%D0%B8 "Теорема Клини"). Этот ответ точный, так как теоремы Клини устанавливают необходимые и достаточные условия представимости последовательности событий в автомате, а именно: выделяются особые множества последовательностей входных символов — [регулярные множества](/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE "Регулярное множество"). Факт появления входной последовательности из такого множества называется соответствующим регулярным событием. Теоремы Клини устанавливают, что в конечном автомате могут быть представлены регулярные события и только они. Таким образом, на языке представления событий ответ на вопрос, что может «делать» конечный автомат, даётся однозначно: конечный автомат может представлять только регулярные события. Ряд важных множеств входных последовательностей, с которыми часто приходится иметь дело на практике, заведомо регулярны. Так, например, заведомо регулярно множество, состоящее из любого конечного числа входных последовательностей конечной длины; множество любых периодических входных последовательностей; множество бесконечных последовательностей, которое содержит заданные конечные последовательности на протяжении нескольких последних тактов, и т. д.

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

Хотя теоремы Клини и отвечают на вопрос о том, что может делать конечный автомат, но отвечают они на этот вопрос неэффективно. Сделаны первые попытки построения иных языков, на которых ответ может быть дан эффективно. Эта проблема языка, играющая кардинальную роль в получении эффективного ответа на вопрос, что может и что не может «делать» конечный автомат, имеет решающее значение и для первых этапов синтеза автомата, то есть для ответа на второй из сформулированных выше вопросов. Если расширить класс динамических систем, которые мы определили терминами «конечный автомат» и «последовательностная машина», включением бесконечной памяти (моделью бесконечной памяти может быть, например, бесконечная лента для хранения символов или бесконечное число состояний), то для динамических систем этого более широкого класса (абстрактные системы этого класса называют [машинами Тьюринга](/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 "Машина Тьюринга")) ответ на вопрос «что они могут делать?» значительно проще — они могут реализовать **любой наперёд заданный алгоритм**. При этом само понятие алгоритма трактуется в современной математике как реализация вычисления значений какой-либо [рекурсивной функции](/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8) "Рекурсивная функция (теория вычислимости)"). Столь однозначный и чёткий ответ на вопрос «что может делать машина Тьюринга?» даёт возможность положить понятие о машине Тьюринга в основу определения понятия алгоритма: алгоритмом называется любой процесс, который может быть осуществлён на конечном автомате, дополненном бесконечной памятью, то есть алгоритмически полных машинах, на машине Тьюринга, на [машине Поста](/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%9F%D0%BE%D1%81%D1%82%D0%B0 "Машина Поста") и др.

## См. также

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=11 "Редактировать раздел «См. также»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=11 "Редактировать код раздела «См. также»")\]

- [Автомат Мили](/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82_%D0%9C%D0%B8%D0%BB%D0%B8 "Автомат Мили")
- [Автомат Мура](/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82_%D0%9C%D1%83%D1%80%D0%B0 "Автомат Мура")
- [JFLAP](/wiki/JFLAP "JFLAP") — кроссплатформенная программа симулятор (автоматов, машины Тьюринга, грамматик)
- [Автоматное программирование](/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 "Автоматное программирование")
- [Sequential Function Chart](/wiki/Sequential_Function_Chart "Sequential Function Chart")
- [Компилятор](/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80 "Компилятор")
- [Транслятор](/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D1%81%D0%BB%D1%8F%D1%82%D0%BE%D1%80 "Транслятор")
- [Сети Петри](/wiki/%D0%A1%D0%B5%D1%82%D0%B8_%D0%9F%D0%B5%D1%82%D1%80%D0%B8 "Сети Петри")
- [Секвенциальная логика](/wiki/%D0%A1%D0%B5%D0%BA%D0%B2%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0 "Секвенциальная логика") (Последовательностная логика)
- [Таблица принятия решений](/wiki/%D0%A2%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0_%D0%BF%D1%80%D0%B8%D0%BD%D1%8F%D1%82%D0%B8%D1%8F_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B9 "Таблица принятия решений")
- [Суффиксный автомат](/wiki/%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Суффиксный автомат")

## Примечания

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=12 "Редактировать раздел «Примечания»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=12 "Редактировать код раздела «Примечания»")\]

1. [↑](#cite_ref-Кузнецов_1-0)_Кузнецов О. П., [Адельсон-Вельский Г. М.](/wiki/%D0%90%D0%B4%D0%B5%D0%BB%D1%8C%D1%81%D0%BE%D0%BD-%D0%92%D0%B5%D0%BB%D1%8C%D1%81%D0%BA%D0%B8%D0%B9,_%D0%93%D0%B5%D0%BE%D1%80%D0%B3%D0%B8%D0%B9_%D0%9C%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%BE%D0%B2%D0%B8%D1%87 "Адельсон-Вельский, Георгий Максимович")_ Автоматы // Дискретная математика для инженера. — М.: Энергия, 1980. — 344 с.
2. [↑](#cite_ref-2)_Айзерман М. А., Гусев Л. А., Розоноэр Л. И., Смирнова И. М., Таль А. А._ Логика. Автоматы. Алгоритмы. Гос. изд. физ.-мат. литературы 1963, 556 стр.

## Литература

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=13 "Редактировать раздел «Литература»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=13 "Редактировать код раздела «Литература»")\]

- _Белоусов А. И., Ткачёв С. Б._ Дискретная математика. — М.: МГТУ, 2006. — С. 460—587. — [ISBN 5-7038-2886-4](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%98%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8_%D0%BA%D0%BD%D0%B8%D0%B3/5703828864).
- _Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман._ Дискретная математика. — 2-е изд. — Вильямс, 2002. — 528 с. — (Алгоритмы и методы. Искусство программирования).
- _Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г._ [Теория и реализация языков программирования](http://trpl7.ru/t-books/TRYAP_BOOK_Details.htm) — М.: МЗ-Пресс, 2006 г., 2-е изд. — [ISBN 5-94073-094-9](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%98%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8_%D0%BA%D0%BD%D0%B8%D0%B3/5940730949)
- Теория автоматов / _Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко_ // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. — М.: ВИНИТИ, 1976. — Т. 13. — С. 109—188. — URL [http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option\_lang=rus](https://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus)
- [Применение конечных автоматов для решения задач автоматизации](http://robot-develop.org/archives/1440#more-1440)
- _[Глушков В. М.](/wiki/%D0%93%D0%BB%D1%83%D1%88%D0%BA%D0%BE%D0%B2,_%D0%92%D0%B8%D0%BA%D1%82%D0%BE%D1%80_%D0%9C%D0%B8%D1%85%D0%B0%D0%B9%D0%BB%D0%BE%D0%B2%D0%B8%D1%87 "Глушков, Виктор Михайлович")_ Синтез цифровых автоматов. — М.: [ГИФМЛ](/wiki/%D0%A4%D0%B8%D0%B7%D0%BC%D0%B0%D1%82%D0%BB%D0%B8%D1%82 "Физматлит"), 1962. — 476 с.

## Ссылки

\[ [править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit&section=14 "Редактировать раздел «Ссылки»") \| [править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&section=14 "Редактировать код раздела «Ссылки»")\]

- _Дехтярь М. И._ [Введение в схемы, автоматы и алгоритмы](http://www.intuit.ru/department/ds/introsaa/)
- [Open source генератор конечных автоматов на языках C++ и Java по XML файлам описания](http://sourceforge.net/projects/genfsm/)
- [Недетерминированные конечные автоматы](http://rsdn.org/article/alg/nka.xml)
- _Подзоров С. Ю._ [Курс лекций по теории алгоритмов](https://web.archive.org/web/20110410034529/http://www.nsu.ru/education/podzorov/Alg/Course.pdf)

[![Перейти к шаблону «Формальные языки»](//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/14px-Wikipedia_interwiki_section_gear_icon.svg.png)](/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B8 "Перейти к шаблону «Формальные языки»")

[Формальные языки](/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA "Формальный язык") и [формальные грамматики](/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 "Формальная грамматика")

Общие понятия

- [Иерархия Хомского](/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE "Иерархия Хомского")
- [Алфавит](/wiki/%D0%90%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82_(%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA) "Алфавит (формальный язык)")
- [Слово](/wiki/%D0%A1%D0%BB%D0%BE%D0%B2%D0%BE_(%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA) "Слово (формальный язык)")

Тип 0

- [Неограниченная грамматика](/wiki/%D0%9D%D0%B5%D0%BE%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 "Неограниченная грамматика")
- [Машина Тьюринга](/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 "Машина Тьюринга")
- [Перечислимый язык](/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%BE_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA "Рекурсивно перечислимый язык")
- [Разрешимый язык](/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA "Рекурсивный язык")

Тип 1

- [Контекстно-зависимая грамматика](/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D0%BE-%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 "Контекстно-зависимая грамматика")
- [Контекстно-зависимый язык](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D0%BE-%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA&action=edit&redlink=1 "Контекстно-зависимый язык (страница отсутствует)")[\[англ.\]](https://en.wikipedia.org/wiki/Context-sensitive_language "en:Context-sensitive language")
- [Линейно ограниченный автомат](/w/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE_%D0%BE%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&redlink=1 "Линейно ограниченный автомат (страница отсутствует)")[\[англ.\]](https://en.wikipedia.org/wiki/Linear_bounded_automaton "en:Linear bounded automaton")

Тип 2

- [Контекстно-свободная грамматика](/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D0%BE-%D1%81%D0%B2%D0%BE%D0%B1%D0%BE%D0%B4%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 "Контекстно-свободная грамматика")
- [Неоднозначная грамматика](/wiki/%D0%9D%D0%B5%D0%BE%D0%B4%D0%BD%D0%BE%D0%B7%D0%BD%D0%B0%D1%87%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 "Неоднозначная грамматика")
- [Контекстно-свободный язык](/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D0%BE-%D1%81%D0%B2%D0%BE%D0%B1%D0%BE%D0%B4%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA "Контекстно-свободный язык")
- [Автомат с магазинной памятью](/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82_%D1%81_%D0%BC%D0%B0%D0%B3%D0%B0%D0%B7%D0%B8%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D1%8C%D1%8E "Автомат с магазинной памятью") ([детерминированный](/w/index.php?title=%D0%94%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82_%D1%81_%D0%BC%D0%B0%D0%B3%D0%B0%D0%B7%D0%B8%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D1%8C%D1%8E&action=edit&redlink=1 "Детерминированный автомат с магазинной памятью (страница отсутствует)")[\[англ.\]](https://en.wikipedia.org/wiki/Deterministic_pushdown_automaton "en:Deterministic pushdown automaton"))
- [Лемма о разрастании](/wiki/%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B4%D0%BB%D1%8F_%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D0%BE-%D1%81%D0%B2%D0%BE%D0%B1%D0%BE%D0%B4%D0%BD%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2 "Лемма о разрастании для контекстно-свободных языков")
- [Лемма Огдена](/wiki/%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%9E%D0%B3%D0%B4%D0%B5%D0%BD%D0%B0 "Лемма Огдена")
- [Теорема Кука](/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D1%83%D0%BA%D0%B0_%D0%BE_%D0%B4%D0%B2%D1%83%D1%81%D1%82%D0%BE%D1%80%D0%BE%D0%BD%D0%BD%D0%B8%D1%85_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0%D1%85 "Теорема Кука о двусторонних автоматах")

Тип 3

- [Регулярная грамматика](/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 "Регулярная грамматика")
- [Регулярный язык](/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA "Регулярный язык")
- [Регулярное выражение](/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F#В_теории_формальных_языков "Регулярные выражения")
- Конечный автомат ( [детерминированный](/wiki/%D0%94%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Детерминированный конечный автомат"), [недетерминированный](/wiki/%D0%9D%D0%B5%D0%B4%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Недетерминированный конечный автомат"))
- [Минимизация ДКА](/wiki/%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%94%D0%9A%D0%90 "Минимизация ДКА")
- [Детерминизация НКА](/w/index.php?title=%D0%94%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%9D%D0%9A%D0%90&action=edit&redlink=1 "Детерминизация НКА (страница отсутствует)")[\[англ.\]](https://en.wikipedia.org/wiki/Powerset_construction "en:Powerset construction")
- [Теорема Майхилла — Нероуда](/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9C%D0%B0%D0%B9%D1%85%D0%B8%D0%BB%D0%BB%D0%B0_%E2%80%94_%D0%9D%D0%B5%D1%80%D0%BE%D1%83%D0%B4%D0%B0 "Теорема Майхилла — Нероуда")

Синтаксический анализ

- [LL-анализатор](/wiki/LL-%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%82%D0%BE%D1%80 "LL-анализатор")
- [LR-анализатор](/wiki/LR-%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%82%D0%BE%D1%80 "LR-анализатор")
- [Метод рекурсивного спуска](/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0 "Метод рекурсивного спуска")
- [Алгоритм Кока — Янгера — Касами](/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BE%D0%BA%D0%B0_%E2%80%94_%D0%AF%D0%BD%D0%B3%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9A%D0%B0%D1%81%D0%B0%D0%BC%D0%B8 "Алгоритм Кока — Янгера — Касами")

[![Перейти к шаблону «External links»](//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/14px-Wikipedia_interwiki_section_gear_icon.svg.png)](/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:External_links "Перейти к шаблону «External links»")

Ссылки на внешние ресурсы

[![Перейти к шаблону «Внешние ссылки»](//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/14px-Wikipedia_interwiki_section_gear_icon.svg.png)](/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:%D0%92%D0%BD%D0%B5%D1%88%D0%BD%D0%B8%D0%B5_%D1%81%D1%81%D1%8B%D0%BB%D0%BA%D0%B8 "Перейти к шаблону «Внешние ссылки»")[![Перейти к элементу Викиданных](//upload.wikimedia.org/wikipedia/commons/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/14px-OOjs_UI_icon_edit-ltr-progressive.svg.png)](https://www.wikidata.org/wiki/Q176452#identifiers "Перейти к элементу Викиданных")

В библиографических каталогах

- [NKC](/wiki/%D0%9D%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B1%D0%B8%D0%B1%D0%BB%D0%B8%D0%BE%D1%82%D0%B5%D0%BA%D0%B0_%D0%A7%D0%B5%D1%88%D1%81%D0%BA%D0%BE%D0%B9_%D0%A0%D0%B5%D1%81%D0%BF%D1%83%D0%B1%D0%BB%D0%B8%D0%BA%D0%B8 "Национальная библиотека Чешской Республики"): [ph210246](https://aleph.nkp.cz/F/?func=find-c&local_base=aut&ccl_term=ica=ph210246&CON_LNG=ENG)

Источник — [https://ru.wikipedia.org/w/index.php?title=Конечный\_автомат&oldid=136323776](https://ru.wikipedia.org/w/index.php?title=Конечный_автомат&oldid=136323776)

[Категории](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B8 "Служебная:Категории"):

- [Конечные автоматы](/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B5_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D1%8B "Категория:Конечные автоматы")
- [Формальные методы](/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B "Категория:Формальные методы")

Скрытые категории:

- [Википедия:Статьи, требующие внесения ясности](/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8,_%D1%82%D1%80%D0%B5%D0%B1%D1%83%D1%8E%D1%89%D0%B8%D0%B5_%D0%B2%D0%BD%D0%B5%D1%81%D0%B5%D0%BD%D0%B8%D1%8F_%D1%8F%D1%81%D0%BD%D0%BE%D1%81%D1%82%D0%B8 "Категория:Википедия:Статьи, требующие внесения ясности")
- [Википедия:Статьи с шаблонами недостатков по алфавиту](/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D1%81_%D1%88%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD%D0%B0%D0%BC%D0%B8_%D0%BD%D0%B5%D0%B4%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%BE%D0%B2_%D0%BF%D0%BE_%D0%B0%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82%D1%83 "Категория:Википедия:Статьи с шаблонами недостатков по алфавиту")
- [Википедия:Статьи без источников (тип: не указан)](/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D0%B1%D0%B5%D0%B7_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2_(%D1%82%D0%B8%D0%BF:_%D0%BD%D0%B5_%D1%83%D0%BA%D0%B0%D0%B7%D0%B0%D0%BD) "Категория:Википедия:Статьи без источников (тип: не указан)")
- [Википедия:Нет источников с июня 2020](/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9D%D0%B5%D1%82_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2_%D1%81_%D0%B8%D1%8E%D0%BD%D1%8F_2020 "Категория:Википедия:Нет источников с июня 2020")
- [Википедия:Статьи с утверждениями без источников более 14 дней](/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D1%81_%D1%83%D1%82%D0%B2%D0%B5%D1%80%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F%D0%BC%D0%B8_%D0%B1%D0%B5%D0%B7_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2_%D0%B1%D0%BE%D0%BB%D0%B5%D0%B5_14_%D0%B4%D0%BD%D0%B5%D0%B9 "Категория:Википедия:Статьи с утверждениями без источников более 14 дней")
- [Страницы, использующие волшебные ссылки ISBN](/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A1%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B,_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D1%83%D1%8E%D1%89%D0%B8%D0%B5_%D0%B2%D0%BE%D0%BB%D1%88%D0%B5%D0%B1%D0%BD%D1%8B%D0%B5_%D1%81%D1%81%D1%8B%D0%BB%D0%BA%D0%B8_ISBN "Категория:Страницы, использующие волшебные ссылки ISBN")

## Навигация

### Персональные инструменты

- Вы не представились системе
- [Обсуждение](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9C%D0%BE%D1%91_%D0%BE%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5 "Страница обсуждений для моего IP [n]")
- [Вклад](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9C%D0%BE%D0%B9_%D0%B2%D0%BA%D0%BB%D0%B0%D0%B4 "Список правок, сделанных с этого IP-адреса [y]")
- [Создать учётную запись](/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%BE%D0%B7%D0%B4%D0%B0%D1%82%D1%8C_%D1%83%D1%87%D1%91%D1%82%D0%BD%D1%83%D1%8E_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C&returnto=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9+%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Мы предлагаем вам создать учётную запись и войти в систему, хотя это и не обязательно.")
- [Войти](/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%92%D1%85%D0%BE%D0%B4&returnto=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9+%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Здесь можно зарегистрироваться в системе, но это необязательно. [o]")

### Пространства имён

- [Статья](/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Просмотреть контентную страницу [c]")
- [Обсуждение](/wiki/%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Обсуждение основной страницы [t]")

русский

### Просмотры

- [Читать](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&stable=1)
- [Текущая версия](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&stable=0&redirect=no "Показать текущую версию этой страницы [v]")
- [Править](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&veaction=edit "Редактировать данную страницу [v]")
- [Править код](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit "Править исходный текст этой страницы [e]")
- [История](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=history "Журнал изменений страницы [h]")

Ещё

### Поиск

[Перейти на заглавную страницу](/wiki/%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0 "Перейти на заглавную страницу")

### Навигация

- [Заглавная страница](/wiki/%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0 "Перейти на заглавную страницу [z]")
- [Содержание](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BE%D0%B4%D0%B5%D1%80%D0%B6%D0%B0%D0%BD%D0%B8%D0%B5)
- [Избранные статьи](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%98%D0%B7%D0%B1%D1%80%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8 "Статьи, считающиеся лучшими статьями проекта")
- [Случайная статья](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0 "Посмотреть случайно выбранную страницу [x]")
- [Текущие события](/wiki/%D0%9F%D0%BE%D1%80%D1%82%D0%B0%D0%BB:%D0%A2%D0%B5%D0%BA%D1%83%D1%89%D0%B8%D0%B5_%D1%81%D0%BE%D0%B1%D1%8B%D1%82%D0%B8%D1%8F "Статьи о текущих событиях в мире")
- [Пожертвовать](//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_ru.wikipedia.org&uselang=ru "Поддержите нас")

### Участие

- [Сообщить об ошибке](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BE%D0%BE%D0%B1%D1%89%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%B1_%D0%BE%D1%88%D0%B8%D0%B1%D0%BA%D0%B0%D1%85 "Сообщить об ошибке в этой статье")
- [Как править статьи](/wiki/%D0%A1%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B0:%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5)
- [Сообщество](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BE%D0%BE%D0%B1%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%BE "О проекте, о том, чем здесь можно заниматься, а также — где что находится")
- [Форум](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A4%D0%BE%D1%80%D1%83%D0%BC "Форум участников Википедии")
- [Свежие правки](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%B2%D0%B5%D0%B6%D0%B8%D0%B5_%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B8 "Список последних изменений [r]")
- [Новые страницы](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9D%D0%BE%D0%B2%D1%8B%D0%B5_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B "Список недавно созданных страниц")
- [Справка](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B0 "Место расположения Справки")

### Инструменты

- [Ссылки сюда](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D1%81%D1%8B%D0%BB%D0%BA%D0%B8_%D1%81%D1%8E%D0%B4%D0%B0/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Список всех страниц, ссылающихся на данную [j]")
- [Связанные правки](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%B2%D1%8F%D0%B7%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B8/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Последние изменения в страницах, на которые ссылается эта страница [k]")
- [Служебные страницы](/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%BF%D0%B5%D1%86%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B "Список служебных страниц [q]")
- [Постоянная ссылка](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&oldid=136323776 "Постоянная ссылка на эту версию страницы")
- [Сведения о странице](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=info "Подробнее об этой странице")
- [Цитировать страницу](/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A6%D0%B8%D1%82%D0%B0%D1%82%D0%B0&page=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&id=136323776&wpFormIdentifier=titleform "Информация о том, как цитировать эту страницу")
- [Получить короткий URL](/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:UrlShortener&url=https%3A%2F%2Fru.wikipedia.org%2Fwiki%2F%25D0%259A%25D0%25BE%25D0%25BD%25D0%25B5%25D1%2587%25D0%25BD%25D1%258B%25D0%25B9_%25D0%25B0%25D0%25B2%25D1%2582%25D0%25BE%25D0%25BC%25D0%25B0%25D1%2582)
- [Скачать QR-код](/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:QrCode&url=https%3A%2F%2Fru.wikipedia.org%2Fwiki%2F%25D0%259A%25D0%25BE%25D0%25BD%25D0%25B5%25D1%2587%25D0%25BD%25D1%258B%25D0%25B9_%25D0%25B0%25D0%25B2%25D1%2582%25D0%25BE%25D0%25BC%25D0%25B0%25D1%2582)
- [Элемент Викиданных](https://www.wikidata.org/wiki/Special:EntityPage/Q176452 "Ссылка на связанный элемент репозитория данных [g]")

### Печать/экспорт

- [Скачать как PDF](/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:DownloadAsPdf&page=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=show-download-screen "Скачать эту страницу как файл PDF")
- [Версия для печати](/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&printable=yes "Версия этой страницы для печати [p]")

### В других проектах

- [Викисклад](https://commons.wikimedia.org/wiki/Category:Finite_state_machine)

### На других языках

- [العربية](https://ar.wikipedia.org/wiki/%D8%A2%D9%84%D8%A9_%D9%85%D8%AD%D8%AF%D9%88%D8%AF%D8%A9_%D8%A7%D9%84%D8%AD%D8%A7%D9%84%D8%A7%D8%AA "آلة محدودة الحالات — арабский")
- [Български](https://bg.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D0%B5%D0%BD_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Краен автомат — болгарский")
- [Bosanski](https://bs.wikipedia.org/wiki/Kona%C4%8Dni_automat "Konačni automat — боснийский")
- [Català](https://ca.wikipedia.org/wiki/Aut%C3%B2mat_finit "Autòmat finit — каталанский")
- [Čeština](https://cs.wikipedia.org/wiki/Kone%C4%8Dn%C3%BD_automat "Konečný automat — чешский")
- [Deutsch](https://de.wikipedia.org/wiki/Endlicher_Automat "Endlicher Automat — немецкий")
- [English](https://en.wikipedia.org/wiki/Finite-state_machine "Finite-state machine — английский")
- [Esperanto](https://eo.wikipedia.org/wiki/Finia_a%C5%ADtomato "Finia aŭtomato — эсперанто")
- [Español](https://es.wikipedia.org/wiki/Aut%C3%B3mata_finito "Autómata finito — испанский")
- [Eesti](https://et.wikipedia.org/wiki/L%C3%B5plik_olekumasin "Lõplik olekumasin — эстонский")
- [Euskara](https://eu.wikipedia.org/wiki/Automata_finitu "Automata finitu — баскский")
- [فارسی](https://fa.wikipedia.org/wiki/%D9%85%D8%A7%D8%B4%DB%8C%D9%86_%D8%AD%D8%A7%D9%84%D8%A7%D8%AA_%D9%85%D8%AA%D9%86%D8%A7%D9%87%DB%8C "ماشین حالات متناهی — персидский")
- [Suomi](https://fi.wikipedia.org/wiki/%C3%84%C3%A4rellinen_automaatti "Äärellinen automaatti — финский")
- [Français](https://fr.wikipedia.org/wiki/Automate_fini "Automate fini — французский")
- [Galego](https://gl.wikipedia.org/wiki/Aut%C3%B3mata_finito "Autómata finito — галисийский")
- [עברית](https://he.wikipedia.org/wiki/%D7%90%D7%95%D7%98%D7%95%D7%9E%D7%98_%D7%A1%D7%95%D7%A4%D7%99 "אוטומט סופי — иврит")
- [Hrvatski](https://hr.wikipedia.org/wiki/Kona%C4%8Dni_automat "Konačni automat — хорватский")
- [Հայերեն](https://hy.wikipedia.org/wiki/%D5%8E%D5%A5%D6%80%D5%BB%D5%A1%D5%BE%D5%B8%D6%80_%D5%A1%D5%BE%D5%BF%D5%B8%D5%B4%D5%A1%D5%BF "Վերջավոր ավտոմատ — армянский")
- [Bahasa Indonesia](https://id.wikipedia.org/wiki/Mesin_finite-state "Mesin finite-state — индонезийский")
- [Italiano](https://it.wikipedia.org/wiki/Automa_a_stati_finiti "Automa a stati finiti — итальянский")
- [日本語](https://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3 "有限オートマトン — японский")
- [ქართული](https://ka.wikipedia.org/wiki/%E1%83%A1%E1%83%90%E1%83%A1%E1%83%A0%E1%83%A3%E1%83%9A%E1%83%98_%E1%83%9B%E1%83%90%E1%83%9C%E1%83%A5%E1%83%90%E1%83%9C%E1%83%90 "სასრული მანქანა — грузинский")
- [한국어](https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%95%9C_%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84 "유한 상태 기계 — корейский")
- [Lombard](https://lmo.wikipedia.org/wiki/Automa_a_stat_finii "Automa a stat finii — Lombard")
- [Lietuvių](https://lt.wikipedia.org/wiki/Baigtinis_automatas "Baigtinis automatas — литовский")
- [Latviešu](https://lv.wikipedia.org/wiki/Gal%C4%ABgs_autom%C4%81ts "Galīgs automāts — латышский")
- [Македонски](https://mk.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%B5%D0%BD_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Конечен автомат — македонский")
- [Mirandés](https://mwl.wikipedia.org/wiki/Out%C3%B3mato_fenito "Outómato fenito — мирандский")
- [Nederlands](https://nl.wikipedia.org/wiki/Eindigetoestandsautomaat "Eindigetoestandsautomaat — нидерландский")
- [Norsk bokmål](https://no.wikipedia.org/wiki/Endelig_tilstandsmaskin "Endelig tilstandsmaskin — норвежский букмол")
- [Polski](https://pl.wikipedia.org/wiki/Automat_sko%C5%84czony "Automat skończony — польский")
- [Português](https://pt.wikipedia.org/wiki/M%C3%A1quina_de_estados_finita "Máquina de estados finita — португальский")
- [Română](https://ro.wikipedia.org/wiki/Automat_finit "Automat finit — румынский")
- [Srpskohrvatski / српскохрватски](https://sh.wikipedia.org/wiki/Kona%C4%8Dni_automat "Konačni automat — сербскохорватский")
- [Slovenčina](https://sk.wikipedia.org/wiki/Kone%C4%8Dn%C3%BD_automat "Konečný automat — словацкий")
- [Српски / srpski](https://sr.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B0%D1%87%D0%B0%D0%BD_%D0%B0%D1%83%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Коначан аутомат — сербский")
- [Svenska](https://sv.wikipedia.org/wiki/%C3%84ndlig_automat "Ändlig automat — шведский")
- [ไทย](https://th.wikipedia.org/wiki/%E0%B9%80%E0%B8%84%E0%B8%A3%E0%B8%B7%E0%B9%88%E0%B8%AD%E0%B8%87%E0%B8%AA%E0%B8%96%E0%B8%B2%E0%B8%99%E0%B8%B0%E0%B8%88%E0%B8%B3%E0%B8%81%E0%B8%B1%E0%B8%94 "เครื่องสถานะจำกัด — тайский")
- [Türkçe](https://tr.wikipedia.org/wiki/Sonlu_durum_makinesi "Sonlu durum makinesi — турецкий")
- [Українська](https://uk.wikipedia.org/wiki/%D0%A1%D0%BA%D1%96%D0%BD%D1%87%D0%B5%D0%BD%D0%BD%D0%B8%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 "Скінченний автомат — украинский")
- [Tiếng Việt](https://vi.wikipedia.org/wiki/M%C3%A1y_tr%E1%BA%A1ng_th%C3%A1i_h%E1%BB%AFu_h%E1%BA%A1n "Máy trạng thái hữu hạn — вьетнамский")
- [中文](https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA "有限状态机 — китайский")
- [粵語](https://zh-yue.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E7%8B%80%E6%85%8B%E6%A9%9F "有限狀態機 — кантонский")

[Править ссылки](https://www.wikidata.org/wiki/Special:EntityPage/Q176452#sitelinks-wikipedia "Править ссылки на другие языки")

- Эта страница в последний раз была отредактирована 23 февраля 2024 в 23:18.
- Текст доступен по [лицензии Creative Commons «С указанием авторства — С сохранением условий» (CC BY-SA)](//creativecommons.org/licenses/by-sa/4.0/deed.ru); в отдельных случаях могут действовать дополнительные условия.
  Подробнее см. [Условия использования](//foundation.wikimedia.org/wiki/Policy:Terms_of_Use/ru).


  Wikipedia® — зарегистрированный товарный знак некоммерческой организации [«Фонд Викимедиа» (Wikimedia Foundation, Inc.)](//wikimediafoundation.org/ru/)

- [Политика конфиденциальности](https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/ru)
- [Описание Википедии](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9E%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B5)
- [Отказ от ответственности](/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9E%D1%82%D0%BA%D0%B0%D0%B7_%D0%BE%D1%82_%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D0%B8)
- [Свяжитесь с нами](//ru.wikipedia.org/wiki/Википедия:Контакты)
- [Кодекс поведения](https://foundation.wikimedia.org/wiki/Policy:Universal_Code_of_Conduct/ru)
- [Разработчики](https://developer.wikimedia.org)
- [Статистика](https://stats.wikimedia.org/#/ru.wikipedia.org)
- [Заявление о куки](https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement)
- [Мобильная версия](//ru.m.wikipedia.org/w/index.php?title=%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&mobileaction=toggle_view_mobile)

- [![Wikimedia Foundation](/static/images/footer/wikimedia-button.svg)](https://wikimediafoundation.org/)
- [![Powered by MediaWiki](/w/resources/assets/poweredby_mediawiki.svg)](https://www.mediawiki.org/)