Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика

Детерминированный конечный автомат

Детерминированный конечный автомат (ДКА, DFA, англ. deterministic finite automaton, DFSA, англ. deterministic finite-state automaton, DFSM англ. deterministic finite-state machine), известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году.

Рисунок иллюстрирует детерминированный конечный автомат с помощью диаграммы состояний. В этом примере имеется три состояния — S0, S1 и S2 (отражены на рисунке окружностями). Автомат на вход принимает конечную последовательность нулей и единиц. Для каждого состояния существует стрелка перехода, ведущая из состояния в другое состояние как для 0, так и для 1. После чтения символа, ДКА детерминированно переходит из одного состояния в другое, следуя по стрелке перехода. Например, если автомат находится в состоянии S0, а входным символом является 1, то автомат детерминированно переходит в состояние S1. ДКА имеет начальное состояние (графически показывается стрелкой «из ниоткуда»), откуда начинается вычисление, и множество конечных состояний (обозначаемых графически в виде двойной окружности), которые определяют, успешно ли закончились вычисления.

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

ДКА распознаёт в точности множество регулярных языков, которые, среди прочего, полезны для лексического анализа и сопоставления с образцом. ДКА могут быть построены из недетерминированного конечного автомата (НКА, англ. nondeterministic finite automata, NFAs) с помощью сведения ДКА к НКА.

Формальное определение

Детерминированный конечный автомат M {displaystyle M} является 5-кортежем ( Q , Σ , δ , q 0 , F ) {displaystyle (Q,Sigma ,delta ,q_{0},F)} , состоящим из

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

Пусть w = a 1 a 2 . . . a n {displaystyle w=a_{1}a_{2}...a_{n}} — строка над алфавитом Σ {displaystyle Sigma } . Автомат M {displaystyle M} принимает строку w {displaystyle w} , если последовательность состояний r 0 , r 1 , . . . , r n {displaystyle r_{0},r_{1},...,r_{n}} существует в Q {displaystyle Q} со следующими условиями

  • r 0 = q 0 {displaystyle r_{0}=q_{0}}
  • r i + 1 = δ ( r i , a i + 1 ) {displaystyle r_{i+1}=delta (r_{i},a_{i+1})} , для i = 0 , . . . , n − 1 {displaystyle i=0,...,n-1}
  • r n ∈ F {displaystyle r_{n}in F} .
  • Словами, первое условие говорит, что машина начинает работу с состояния q 0 {displaystyle q_{0}} . Второе условие говорит, что для данного символа строки w {displaystyle w} машина переходит из состояния в состояние согласно функции переходов δ {displaystyle delta } . Последнее условие говорит, что машина принимает w {displaystyle w} , если последний входной символ строки w {displaystyle w} вынуждает машину перейти в одно из конечных состояний. В противном случае говорят, что автомат отвергает строку. Множество строк, которые принимает M {displaystyle M} , является языком, распознаваемым автоматом M {displaystyle M} , и этот язык обозначается L ( M ) {displaystyle L(M)} .

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

    Для более полного формального определения см. статью «Теория автоматов».

    Полные и неполные автоматы

    Согласно вышеприведённому определению, детерминированные конечные автоматы всегда полные — они определяют переход для каждого состояния и для каждого входного символа.

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

    Пример

    Следующий пример является ДКА M {displaystyle M} с двоичным алфавитом, который требует, чтобы вход содержал чётное число нулей.

    M = ( Q , Σ , δ , q 0 , F ) {displaystyle M=(Q,Sigma ,delta ,q_{0},F)} где

    • Q = { S 1 , S 2 } {displaystyle Q={S_{1},S_{2}}}
    • Σ = { 0 , 1 } {displaystyle Sigma ={0,1}}
    • q 0 = S 1 {displaystyle q_{0}=S_{1}}
    • F = { S 1 } {displaystyle F={S_{1}}} и
    • δ {displaystyle delta } определяется следующей таблицей переходов:

    Конечное состояние S 1 {displaystyle S_{1}} соответствует чётному числу нулей во входной строке, в то время как S 2 {displaystyle S_{2}} говорит о нечётном числе. 1 во входном потоке не изменяет состояние автомата. Когда входная строка заканчивается, конечное состояние покажет, содержала ли входная строка чётное число нулей, или нет. Если входная строка содержит чётное число нулей, M {displaystyle M} закончит в конечном состоянии S 1 {displaystyle S_{1}} , так что входная строка будет принята.

    Язык, распознаваемый M {displaystyle M} , является регулярным языком, определяемым регулярным выражением ((1*) 0 (1*) 0 (1*))*, где * является звездой Клини, например 1* означает любое число (возможно, равное нулю) последовательных единиц.

    Свойства замкнутости

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

    • Объединение
    • Пересечение (см. рисунок)
    • Конкатенация
    • Дополнение
    • замыкание Клини
    • Обращение
    • Итерация
    • Разность
    • Подстановка
    • Гомоморфизм

    Для каждой операции оптимальное построение с учётом числа состояний определяется в исследовании позиционной сложности.

    Поскольку ДКА эквивалентны недетерминированным конечным автоматам (НКА, англ. nondeterministic finite automata, NFA), эти замыкания могут быть доказаны с помощью свойств замыканий НКА.

    Как моноид переходов

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

    Для данного входного символа a ∈ Σ {displaystyle ain Sigma } можно построить функцию перехода δ a : Q → Q {displaystyle delta _{a}:Q ightarrow Q} путём определения δ a ( q ) = δ ( q , a ) {displaystyle delta _{a}(q)=delta (q,a)} для всех q ∈ Q {displaystyle qin Q} . (Этот приём называется каррированием.) В этом ракурсе δ a {displaystyle delta _{a}} «действует» на состояние Q с получением другого состояния. Можно рассматривать результат суперпозиции функций, последовательно применённых к различным функциям δ a {displaystyle delta _{a}} , δ b {displaystyle delta _{b}} и так далее. Если дана пара букв a , b ∈ Σ {displaystyle a,bin Sigma } , можно определить новую функцию δ ^ a b = δ a ∘ δ b {displaystyle {widehat {delta }}_{ab}=delta _{a}circ delta _{b}} , где ∘ {displaystyle circ } обозначает суперпозицию функций.

    Ясно, что этот процесс может быть рекурсивно продолжен, давая следующее рекурсивное определение δ ^ : Q × Σ ⋆ → Q {displaystyle {widehat {delta }}:Q imes Sigma ^{star } ightarrow Q} :

    δ ^ ( q , ϵ ) = q {displaystyle {widehat {delta }}(q,epsilon )=q} , где ϵ {displaystyle epsilon } является пустой строкой, а δ ^ ( q , w a ) = δ a ( δ ^ ( q , w ) ) {displaystyle {widehat {delta }}(q,wa)=delta _{a}({widehat {delta }}(q,w))} , где w ∈ Σ ∗ , a ∈ Σ {displaystyle win Sigma ^{*},ain Sigma } и q ∈ Q {displaystyle qin Q} .

    Функция δ ^ {displaystyle {widehat {delta }}} определена для всех слов w ∈ Σ ∗ {displaystyle win Sigma ^{*}} . Работа ДКА является последовательностью суперпозиций δ ^ {displaystyle {widehat {delta }}} на себя.

    Повторение суперпозиций функций образует моноид. Для функций перехода этот моноид известен как Моноид переходов, или, иногда, как полугруппа преобразований. Построение может быть обращено — если дана δ ^ {displaystyle {widehat {delta }}} , можно реконструировать δ {displaystyle delta } , так что эти два описания эквивалентны.

    Локальные автоматы

    Локальный автомат — это ДКА, для которого все дуги с той же меткой ведут в одну вершину. Локальные автоматы принимают класс формальных языков, для которых принадлежность слова к языку определяется «скользящим окном» длины два на слове

    Граф Майхилла над алфавитом A — это ориентированный граф с множеством вершин A и подмножеством вершин, помеченных как «начальная» и «конечная». Язык, принимаемый графом Майхилла, является множеством ориентированных путей из начальной вершины в конечную — граф тогда работает как автомат. Класс языков, воспринимаемый графами Майхилла является классом локальных языков.

    Стохастика в ДКА

    Когда начальное состояние и конечные состояния игнорируются, ДКА с n {displaystyle n} состояниями и алфавитом размера k {displaystyle k} можно рассматривать как орграф с n {displaystyle n} вершинами, в котором все вершины имеют k {displaystyle k} исходящих дуг с метками 1 , … , k {displaystyle 1,ldots ,k} (орграф с k {displaystyle k} исходами). Известно, что когда k ⩾ 2 {displaystyle kgeqslant 2} является фиксированным целым, с высокой вероятностью наибольшая компонента сильной связности (англ. strongly connected component, SCC), в которой орграф с k {displaystyle k} исходами выбран равномерно случайно, имеет линейный размер и может быть достигнут из любой вершины. Было также доказано, что при возрастании k {displaystyle k} по мере роста n {displaystyle n} , весь орграф имеет фазовый переход к сильной связности подобно модели Эрдёша — Реньи для связности.

    В случайном ДКА максимальное число вершин, достижимых из одной вершины с высокой вероятностью очень близко к числу вершин в наибольшей компоненте сильной связности. Это также верно для наибольшего порождённого подграфа с минимальной полустепенью захода единица, который можно рассматривать как ориентированную версию 1 {displaystyle 1} -ядра.

    Преимущества и недостатки

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

    • дополнение языка, распознаваемого данным ДКА.
    • объединение/пересечение языков, распознаваемых двумя данными ДКА.

    Поскольку ДКА могут быть сведены канонической форме (минимальных ДКА), есть также два эффективных алгоритма определения

    • принимает ли ДКА какую-либо строку (Задача проверки пустоты)
    • принимает ли ДКА все строки (Задача проверки универсальности)
    • принимают ли два ДКА один и тот же язык (Задача проверки эквивалентности)
    • содержится ли язык, распознаваемый ДКА, в язык, распознаваемый другим ДКА (Задача проверки включения)
    • ДКА с минимальным числом состояний для конкретного регулярного языка (Задача минимизации)

    ДКА эквивалентны по вычислительным возможностям недетерминированным конечным автоматам (НКА, англ. nondeterministic finite automata, NFAs). Это потому, во-первых, что любой ДКА является также и НКА, так что НКА может делать всё, что может делать ДКА. Также, если дан НКА, с помощью сведения ДКА к НКА можно построить ДКА, который распознаёт тот же самый язык, что и НКА, хотя ДКА может иметь экпоненциально большее число состояний, чем НКА. Однако даже при вычислительной эквивалентности НКА автоматам ДКА, вышеупомянутые задачи не обязательно решаются эффективно для НКА. Задача неуниверсальности для НКА имеет сложность PSPACE, поскольку имеются небольшие НКА с отклоняемыми наименьшими словами экспоненциального размера. ДКА является универсальным тогда и только тогда, когда все состояния являются конечными, но это неверно для НКА. Задачи эквивалентности, включения и минимизации также имеют сложность PSPACE, поскольку они требуют формирования дополнения НКА, что приводит к экспоненциальному взрыву размера.

    С другой стороны, конечные автоматы сильно ограничены в языках, которые они распознают. Много простых языков, включая любую задачу, требующую более чем постоянной памяти для решения, не могут быть распознаны ДКА. Классическим примером простого языка, который не может распознать никакой ДКА, являются скобки или язык Дика, то есть язык, который состоит из правильно расставленных скобок, как в слове «(()())». Интуитивно ясно, что никакой ДКА не может распознать язык Дика, поскольку ДКА не в состоянии делать подсчёты — подобным ДКА автоматам нужно состояние, представляющее любое возможное число «открытых» скобок, что означает, что нужно иметь неограниченное число состояний. Другим простым примером является язык, состоящий из строк вида a n b n {displaystyle a^{n}b^{n}} для некоторого конечного, но произвольно большого числа букв a с последующим равным числом букв b.