1303
правки
Конечный автомат: различия между версиями
Материал из WikiGrapp
→Литература
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| (не показано 7 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Конечный автомат''' ([[Finite-state automation]]) — | '''Конечный автомат''' (''[[Finite-state automaton|Finite-state automaton,]] [[Finite automation]]'') — [[абстрактная машина]], используемая для задания [[регулярные множества| ''регулярных множеств'']]. '''Конечный автомат''' состоит из входной ленты, входной головки и | ||
управляющего устройства. Входная лента — это линейная последовательность клеток, или ячеек, каждая из которых | |||
управляющего устройства. Входная лента — это линейная | |||
последовательность клеток, или ячеек, каждая из которых | |||
может содержать любой символ из <math>\,\Sigma</math>. В каждый данный | может содержать любой символ из <math>\,\Sigma</math>. В каждый данный | ||
момент входная головка читает, или, как иногда говорят, | момент входная головка читает, или, как иногда говорят, | ||
| Строка 28: | Строка 26: | ||
(3) <math>\,\delta</math> — отображение множества <math>\,Q\times\Sigma</math> в | (3) <math>\,\delta</math> — отображение множества <math>\,Q\times\Sigma</math> в | ||
множество подмножеств <math>\,Q</math>, называемое ''функцией переходов''; | множество подмножеств <math>\,Q</math>, называемое ''[[Функция переходов|функцией переходов]]''; | ||
(4) <math>q_0\in Q</math> — выделенное [[Начальное состояние автомата|''начальное состояние'']]; | (4) <math>q_0\in Q</math> — выделенное [[Начальное состояние автомата|''начальное состояние'']]; | ||
| Строка 56: | Строка 54: | ||
<math>(q_0,\omega)\vdash_{M}^{*}(q,e)</math> для некоторого <math>q\in F</math>. | <math>(q_0,\omega)\vdash_{M}^{*}(q,e)</math> для некоторого <math>q\in F</math>. | ||
Языком, ''определяемым'' (''распознаваемым'', ''допускаемым'') | Языком, ''[[Язык, определяемый автоматом|определяемым]]'' (''[[Язык, распознаваемый автоматом|распознаваемым]]'', ''[[Язык, допускаемый автоматом|допускаемым]]'') автоматом <math>M</math> (обозначается <math>L(M)</math>), называется множество | ||
автоматом <math>M</math> (обозначается <math>L(M)</math>), называется множество | |||
входных цепочек, допускаемых автоматом <math>M</math>, т.е. | входных цепочек, допускаемых автоматом <math>M</math>, т.е. | ||
<math>L(M)=\{\omega:\omega\in\Sigma^*</math> и | <math>L(M)=\{\omega:\omega\in\Sigma^*</math> и | ||
| Строка 64: | Строка 61: | ||
Часто бывает удобно использовать графическое представление | Часто бывает удобно использовать графическое представление | ||
'''конечного автомата''' в виде так называемой [[Диаграмма конечного автомата|''диаграммы'']] | '''конечного автомата''' в виде так называемой [[Диаграмма конечного автомата|''диаграммы'']] (или [[Граф переходов автомата|''графа переходов'']]) автомата — [[орграф|''орграфа'']], [[вершина|''вершины'']] которого помечены символами состояний и в котором есть дуга <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> помечается списком, состоящим из | ||
| Строка 88: | Строка 82: | ||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | * Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | ||
* Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: НГУ, 2018. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | * Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | ||
[[Категория: Теория автоматов]] | [[Категория: Теория автоматов]] | ||
[[Категория:Потоковый анализ программ]] | |||
[[Категория:Преобразование программ]] | |||
[[Категория:Основные термины]] | |||
[[Категория:Теория формальных языков]] | |||
