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

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

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

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

Содержание

Терминология [ править | править код ]

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

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

Детерминированный конечный автомат (ДКА) — последовательность (кортеж) из пяти элементов ( Q , Σ , δ , S 0 , F ) <displaystyle (Q,Sigma ,delta ,S_<0>,F)>, где:

  • Q <displaystyle Q>— множество состояний автомата
  • Σ <displaystyle Sigma >— алфавит языка, который понимает автомат
  • δ <displaystyle delta >— функция перехода, такая что δ : Q × Σ → Q <displaystyle delta :Q imes Sigma
    ightarrow Q>
  • S 0 ∈ Q <displaystyle S_<0>in Q>— начальное состояние
  • F ⊆ Q <displaystyle Fsubseteq Q>— множество конечных состояний.

Недетерминированный конечный автомат (НКА) — последовательность (кортеж) из пяти элементов ( Q , Σ , Δ , S , F ) <displaystyle (Q,Sigma ,Delta ,S,F)>, где:

  • Q <displaystyle Q>— множество состояний автомата
  • Σ <displaystyle Sigma >— алфавит языка, который понимает автомат
  • Δ <displaystyle Delta >— отношение перехода, :q,pin Q,ain Sigma cup \>>"> Δ = < q , a , p >: q , p ∈ Q , a ∈ Σ ∪ < e >><displaystyle Delta =< :q,pin Q,ain Sigma cup \>>:q,pin Q,ain Sigma cup \>>"/> , где < e ><displaystyle >— пустое слово. То есть, НКА может совершить скачок из состояния q в состояние p, в отличие от ДКА, через пустое слово, а также перейти из q по a несколько состояний (что опять же в ДКА невозможно)
  • S ⊆ Q <displaystyle Ssubseteq Q>— множество начальных состояний
  • F ⊆ Q <displaystyle Fsubseteq Q>— множество конечных состояний.

Слово Автомат читает конечную строку символов a1,a2,…., an , где ai ∈ Σ, которая называется входным словом. Набор всех слов записывается как Σ*. Принимаемое слово Слово w ∈ Σ* принимается автоматом, если qn ∈ F.

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

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

Применение [ править | править код ]

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

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

Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и сложности задач.

Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рас­суждения и легкость программной или аппаратной реализации.

Читайте также:  Что вставляют в розетку как называется

С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.

У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.

Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.

  • По горизонтали вверху находятся возможные входные символы.
  • По вертикали слева находятся текущие возможные состояния.

Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ ‘a’, из состояния 1 в состояние 2, если символ ‘b’.

Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.

Стартовое состояние — состояние откуда КА начинает свою работу.

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

Детерминированные конечные автоматы (deterministic finite automaton)

Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.

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

Недетерминированные конечные автоматы (nondeterministic finite automaton)

НКА не является каким-то существенным улучшением ДКА, просто в нем добавлен так сказать синтаксический сахар, в виде свободных переходов, недетерминированности и множеств состояний. Реализовать можно как массив состоящий из структур в которой хранится состояние, входной символ и следующее состояние.

Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.

Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.

Множества состояний — в один момент времени НКА может находится в нескольких состояниях.

Заключительное состояние обозначается двойным кругом.

В стартовом состоянии у нас текущим состоянием является <1>, при входном символе ‘b’ у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа ‘b’ текущим состоянием является множество <1, 2>.

Свободным переходом обозначается пунктирной линией.

Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии <2, 4>.

Для преобразования НКА в ДКА используется алгоритм Томпсона.
При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.

Это тот же КА, но с дополнительной памятью в виде стека. Теперь для совершения перехода нужно учитывать еще несколько факторов, символ который нужно удалить из стека и символы которые нужно добавить в стек.

КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стека (я понимаю, что память тоже конечна).

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

Добавление символов в стек — при любом переходе решает какие символы добавить в стек.

  • Детерминированные — к нему применяются те же правила как к ДКА к тому же завершает работу только в заключительном состоянии.
  • Недетерминированные — к нему применяются те же правила как к НКА к тому же он может завершать работу в заключительном состоянии или когда стек станет пуст.
Читайте также:  Что означает разбитый телефон во сне

Шаблон: входной_символ; удаляемый_символ/добавляемый символ. На дно стека добавляется символ $ для, того, что понять когда он закончился.

Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.

ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.

Самая мощная машина из существующих, его преимущество перед другими в ленте с которой он может работать как хочет. В нем нет свободных переходов. Умеет интерпретировать другие автоматы такие как КА, КАМП.

Лента — это одномерный массив в который могут записываться данные за счет головки над ячейкой, который можно заранее заполнить входными данными.

Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются ‘_’.

Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.

  1. Если находится в состоянии 1 и прочитан нуль, записать еди­ницу, сдвинуть вправо и перейти в состояние 2.
  2. Если находится в состоянии 1 и прочитана единица, записать нуль, сдвинуть влево и перейти в состояние 1.
  3. Еcли находится в состоянии 1 и прочитан пустой квадратик, записать единицу, сдвинуть вправо и перейти в состояние 2.
  4. Если находится в состоянии 2 и прочитан нуль, записать нуль, сдвинуть вправо и остаться в состояние 2.
  5. Если находится в состоянии 2 и прочитана единица, записать единицу, сдвинуть вправо и остаться в состояние 2.
  6. Если находится в состоянии 2 и прочитать пустой квадратик, записать пустой квадратик, сдвинуть влево и перейти в состоя­ние 3.

ДМТ эквивалентен НМТ, так, что они тоже не различаются.

Универсальная машина Тьюринга (universal Turing machine)

Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.

  1. Память порождаемой машины не может быть больше, чем у самой УМТ.
  2. Нужно уметь правильно разделять пространство ленты между порождаемой машиной и УМТ, ведь их данные находятся на одной ленте.

На этом введение в автоматы закончено, теперь вы можете продолжить изучать дальнейший материал сами.

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

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

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

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

Читайте также:  Acer aspire 7720g видеокарта

Абстрактный автомат – это математическая модель цифрового автомата, задаваемая шестикомпонентным вектором S=(A,Z,W,d,l,a1), где А=a,…,am> – множество внутренних состояний абстрактного автомата; Z=[z1,…,zk> и W=1,…,wl> – соответственно множества входных и выходных абстрактных слов; d — функция переходов; l — функция выходов; a1 – начальное состояние автомата. Абстрактный автомат может быть представлен как устройство с одним входом и одним выходом (рис. 35), на которые подаются абстрактные входные слова и формируются абстрактные выходные слова.

Понятие состояние автомата используется для описания систем, выходы которых зависят не только от входных сигналов, но и от предыстории, то есть информации о том, что происходило с автоматом в предыдущий интервал времени. Состояние автомата позволяет устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входных сигналов.

По виду функции выходов все множество автоматов можно подразделить на два класса: автоматы Мили и автоматы Мура.

Автоматами Мура, или автоматами первого типа, называют автоматы, для которых абстрактное выходное слово w(t) не зависит явно от входного слова z(t), а определяется только состоянием автомата в момент времени t. Закон функционирования автомата Мура может быть описан системой уравнений:

К автоматам второго типа, или автоматам Мили, относятся автоматы, поведение которых может быть описано системой уравнений:

Следовательно, в отличие от автомата Мура для автомата Мили выходной символ w(t) зависит не только от текущего состояния, но и от входного символа.

Между моделями автоматов Мили и Мура существует соответствие, позволяющее преобразовать закон функционирования одного из них в другой.

Совмещенная модель автомата (С-автомат). Абстрактный С-автомат – математическая модель дискретного устройства, определяемого вектором S=(A,Z,W,U,d,l1,l2,a1), где А, Z, d и а1 определены выше, а W=1,…,wl> и U=1,…,ul> – выходной абстрактный алфавит автомата Мили и Мура соответственно, l1 и l2 — функции выходов. Абстрактный С-автомат может быть представлен как устройство с одним входом, на который поступают слова из входного алфавита Z, и двумя выходами (рис. 36), на которых формируются абстрактные выходные слова из выходных алфавитов W и U.

Отличие С-автомата от моделей автоматов Мили и Мура заключается в том, что он одновременно реализует две функции выходов l1 и l2, каждая из которых характерна для одной из двух моделей.

Автомат S называется конечным, если конечны множества A, Z и W, и детерминированным, если, находясь в некотором состоянии, он не может перейти более чем в одно состояние под действием одного и того же входного символа. Если в автомате выделено начальное состояние а1, то он называется инициальным. Состояние аs называется устойчивым, если для любого zkÎZ, такого что as=d(am,zk), as=d(as,zk), то есть если автомат из состояния am в перешел в состояние as под действием входного слова zk , то выйти из этого состояния он может только под действием другого входного слова. Автомат S является асинхронным, если каждое его состояние устойчиво, иначе синхронным. Автомат называется полностью определенным, если область определения функции d совпадает с множеством пар (am,zk), а функции l для автомата Мили − с множеством пар (am,zk), Мура − с множеством am. У частичного автомата функции d и l определены не для всех пар.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8955 — | 7622 — или читать все.

Ссылка на основную публикацию
Adblock detector