1288
правок
Конечный автомат: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Конечный автомат''' ([[Finite-state automaton]]) — распознаватель, | '''Конечный автомат''' (''[[Finite-state automaton|Finite-state automaton,]] [[Finite automation]]'') — распознаватель, | ||
используемый для задания [[регулярные множества| ''регулярных множеств'']]. '''Конечный автомат''' состоит из входной ленты, входной головки и | используемый для задания [[регулярные множества| ''регулярных множеств'']]. '''Конечный автомат''' состоит из входной ленты, входной головки и | ||
управляющего устройства. Входная лента — это линейная | управляющего устройства. Входная лента — это линейная | ||
| Строка 64: | Строка 64: | ||
Часто бывает удобно использовать графическое представление | Часто бывает удобно использовать графическое представление | ||
'''конечного автомата''' в виде так называемой [[Диаграмма конечного автомата|''диаграммы'']] | '''конечного автомата''' в виде так называемой [[Диаграмма конечного автомата|''диаграммы'']] (или [[Граф переходов автомата|''графа переходов'']]) автомата — [[орграф|''орграфа'']], [[вершина|''вершины'']] которого помечены символами состояний и в котором есть дуга <math>\,(p,q)</math>, если | ||
(или [[Граф переходов автомата|''графа переходов'']]) автомата — | |||
[[орграф|''орграфа'']], [[вершина|''вершины'']] которого помечены | |||
символами состояний и в котором есть дуга <math>\,(p,q)</math>, если | |||
существует такой символ <math>a\in\Sigma</math>, что <math>q\in\delta(p,a)</math>. | существует такой символ <math>a\in\Sigma</math>, что <math>q\in\delta(p,a)</math>. | ||
Кроме того, дуга <math>\,(p,q)</math> помечается списком, состоящим из | Кроме того, дуга <math>\,(p,q)</math> помечается списком, состоящим из | ||