1303
правки
Конечный автомат: различия между версиями
Материал из WikiGrapp
→Литература
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Конечный автомат''' (''[[Finite-state automaton|Finite-state automaton,]] [[Finite automation]]'') — | '''Конечный автомат''' (''[[Finite-state automaton|Finite-state automaton,]] [[Finite automation]]'') — [[абстрактная машина]], используемая для задания [[регулярные множества| ''регулярных множеств'']]. '''Конечный автомат''' состоит из входной ленты, входной головки и | ||
управляющего устройства. Входная лента — это линейная последовательность клеток, или ячеек, каждая из которых | |||
управляющего устройства. Входная лента — это линейная | |||
последовательность клеток, или ячеек, каждая из которых | |||
может содержать любой символ из <math>\,\Sigma</math>. В каждый данный | может содержать любой символ из <math>\,\Sigma</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>M</math>, т.е. | ||
<math>L(M)=\{\omega:\omega\in\Sigma^*</math> и | <math>L(M)=\{\omega:\omega\in\Sigma^*</math> и | ||
| Строка 84: | Строка 82: | ||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | * Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | ||
* Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: НГУ, 2018. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | * Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | ||
[[Категория: Теория автоматов]] | [[Категория: Теория автоматов]] | ||
[[Категория:Потоковый анализ программ]] | |||
[[Категория:Преобразование программ]] | |||
[[Категория:Основные термины]] | |||
[[Категория:Теория формальных языков]] | |||
