Теория автоматов

Август 22, 2022

Главная
Математика
Теория автоматов

Содержание

2. Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических
3. Символ — любой атомарный блок данных, который может производить эффект на машину. Чаще всего символ —
4. Автоматы могут быть: Детерминированные Недетерминированные
5. Детерминированный конечный автомат (ДКА) — последовательность (кортеж) из пяти элементов (Q , Σ , δ ,
6. Недетерминированный конечный автомат (НКА) — последовательность (кортеж) из пяти элементов (Q , Σ , ∆, S,
7. СЛОВО Автомат читает конечную строку символов a1,a2,…., an , где ai ∈ Σ, которая называется входным
8. ПРИНИМАЕМОЕ СЛОВО
9. ПРИМЕНЕНИЕ Теория автоматов лежит в основе всех цифровых технологий и программного обеспечения, так например компьютер является
11. Скачать презентацию

Слайд 2

Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде

математических моделей — и задачи, которые они могут решать.
Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма.

Слайд 3

Символ — любой атомарный блок данных, который может производить эффект на машину.

Чаще всего символ — это буква обычного языка, но может быть, к примеру, графическим элементом диаграммы.

Слово — строка символов, создаваемая через конкатенацию (соединение).
Алфавит — конечный набор различных символов (множество символов)
Язык — множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.

Слайд 4

Автоматы могут быть:
Детерминированные
Недетерминированные

Слайд 5

Детерминированный конечный автомат (ДКА) — последовательность (кортеж) из пяти элементов (Q , Σ ,

δ , S0, F), где:

Слайд 6

Недетерминированный конечный автомат (НКА) — последовательность (кортеж) из пяти элементов (Q , Σ ,

∆, S, F), где:

Q — множество состояний автомата
Σ — алфавит языка, который понимает автомат
∆ — отношение перехода
S С Q — множество начальных состояний
F C Q — множество конечных состояний.

Слайд 7

СЛОВО
Автомат читает конечную строку символов a1,a2,…., an , где ai ∈ Σ, которая называется входным словом. Набор

всех слов записывается как Σ*.

Слайд 8

ПРИНИМАЕМОЕ СЛОВО

Слайд 9

ПРИМЕНЕНИЕ
Теория автоматов лежит в основе всех цифровых технологий и программного

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