Математический аппарат теории автоматов используется в. Теория автоматов.docx - Теория автоматов

Вычислительные машины, представленные в виде математических моделей - и задачи, которые они могут решать.

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

Энциклопедичный YouTube

1 / 3

✪ Урок 12. Основы теории автоматов. Математическая логика. Уроки по информатике

✪ Как управлять миром, изучив всего одну простую модель!

✪ Урок 15. Решение прикладных задач по теории автоматов. Математическая логика. Уроки по информатике

Субтитры

Терминология

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

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

Автоматы Детерминированный конечный автомат (ДКА) - последовательность (кортеж) из пяти элементов (Q , Σ , δ , S 0 , F) {\displaystyle (Q,\Sigma ,\delta ,S_{0},F)} , где: Недетерминированный конечный автомат (НКА) - последовательность (кортеж) из пяти элементов (Q , Σ , Δ , S , F) {\displaystyle (Q,\Sigma ,\Delta ,S,F)} , где: Слово Автомат читает конечную строку символов a 1 ,a 2 ,…., a n , где a i ∈ Σ, которая называется входным словом .Набор всех слов записывается как Σ*. Принимаемое слово Слово w ∈ Σ* принимается автоматом, если q n ∈ F.

Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита Σ {\displaystyle \Sigma } таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:

L = { w ∈ Σ ⋆ | δ ^ (S 0 , w) ∈ F } {\displaystyle L=\{w\in \Sigma ^{\star }|{\hat {\delta }}(S_{0},w)\in F\}}

Обычно автомат переходит из состояния в состояние с помощью функции перехода δ {\displaystyle \delta } , читая при этом один символ из ввода. Есть автоматы, которые могут перейти в новое состояние без чтения символа. Функция перехода без чтения символа называется ϵ {\displaystyle \epsilon } -переход (эпсилон-переход).сложности задач.

Типовые задачи

• Построение и минимизация автоматов - построение абстрактного автомата из заданного класса, решающего заданную задачу (принимающего заданный язык), возможно, с последующей минимизацией по числу состояний или числу переходов.
• Синтез автоматов - построение системы из заданных «элементарных автоматов», эквивалентной заданному автомату. Такой автомат называется структурным . Применяется, например, при синтезе цифровых электрических схем на заданной элементной базе.

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

Под термином автомат можно понимать некоторое реально существующее устройство, функционирующее на основании как сигналов о состоянии внешней среды, так и внутренних сигналов о состоянии самого автомата. В этом плане ЭВМ может быть рассмотрена как цифровой автомат. Под цифровым автоматом понимается устройство, предназначенное для преобразования цифровой информации. С другой стороны, под термином автомат можно понимать математическую модель некоторого устройства. Общая теория автоматов подразделяется на две части: абстрактную и структурную теорию автоматов. Различие между ними состоит в том, что абстрактная теория абстрагируется от структуры как самого автомата, так и входных и выходных сигналов. В абстрактной теории анализируются переходы автомата под воздействием абстрактных входных слов и формируемые на этих переходах абстрактные выходные слова.

В структурной теории рассматривается структура как самого автомата, так и его входных и выходных сигналов, способы построения автоматов из элементарных автоматов, способы кодирования входных и выходных сигналов, состояний автомата.

В соответствии с этим принято различать две модели автоматов: структурную и абстрактную. Абстрактная модель применяется при теоретическом рассмотрении автоматов. Структурная модель служит для построения схемы автомата из логических элементов и триггеров и предназначена для выполнения функции управления.

Абстрактный автомат – это математическая модель цифрового автомата, задаваемая шестикомпонентным вектором S=(A,Z,W,d,l,a 1), где А={a a ,…,a m } – множество внутренних состояний абстрактного автомата; Z=}