НКА

НКА

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

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: \boldsymbol{M = (Q , \Sigma , \delta , q_0 , F)} где:

  • Q — конечное множество состояний автомата;
  • q0 — начальное состояние автомата ( q_0 \in Q);
  • F — множество заключительных (или допускающих) состояний, таких что F \subset Q;
  • Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
  • δ — заданное отображение множества Q \times \Sigma во множество \mathcal {P} (Q) подмножеств Q:
    \delta : Q \times \Sigma \rightarrow \mathcal {P} (Q)
    (иногда δ называют функцией переходов автомата).

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

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

Содержание

Другие способы описания

  1. Диаграмма состояний (или иногда граф переходов) — графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого — состояния КА, дуги — переходы из одного состояния в другое, а нагрузка — символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой должны быть надписаны все они.
  2. Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

Детерминированный конечный автомат
  • Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.


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

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

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

Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет — так называется множество слов, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.

См. также

Ссылки

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "НКА" в других словарях:

  • ёнка — сущ., кол во синонимов: 1 • енка (2) Словарь синонимов ASIS. В.Н. Тришин. 2013 …   Словарь синонимов

  • ёнка — (женщина однодворка) (Даль) …   Словарь употребления буквы Ё

  • інка — іменник чоловічого або жіночого роду, істота …   Орфографічний словник української мови

  • НКА — НДКА НКА недетерминированный конечный автомат НКА никель кадмиевый аккумулятор НКА национально культурная автономия НКА Национальная концертная академия …   Словарь сокращений и аббревиатур

  • НКА РК — Казкосмос НКА РК Национальное космическое агентство Республики Казахстан Казахстан, косм. Казкосмос Источник: http://www.spaceres.kz/ …   Словарь сокращений и аббревиатур

  • НКА — национально культурная автономия никель кадмиевый аккумулятор …   Словарь сокращений русского языка

  • Киноплёнка — У этого термина существуют и другие значения, см. Плёнка. Киноплёнка  перфорированная по краям лента из прозрачного и гибкого материала (подложки), предназначенная[1] для записи движущегося изображения и звука. В большинстве случаев на… …   Википедия

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

  • Фотоплёнка — У этого термина существуют и другие значения, см. Плёнка. Фотоплёнка, заряженная в фотоаппарат …   Википедия

  • Права ребёнка — Права   Теория Естественные и законные права Права требования и права свободы Отрицательные и положительные права Индивидуальные и групповые п …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»