Конечные автоматы | это... Что такое Конечные автоматы? (original) (raw)
Конечные автоматы
Конечные автоматы
Конечный автомат — в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно. Конечный автомат является частным случаем абстрактного автомата.
Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: где:
Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».
Конечные автоматы широко используются на практике, например в синтаксических, лексических анализаторах, и тестировании программного обеспечения на основе моделей.
Содержание
- 1 Другие способы описания
- 2 Детерминированность
- 3 Автоматы и регулярные языки
- 4 См. также
- 5 Ссылки
- 6 Ссылки
Другие способы описания
- **Диаграмма состояний (**или иногда граф переходов) — графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого — состояния КА, дуги — переходы из одного состояния в другое, а нагрузка — символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой должны быть надписаны все они.
- Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.
Детерминированность
Конечные автоматы подразделяются на детерминированные и недетерминированные.
Детерминированный конечный автомат
- Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
- Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:
Существуют переходы, помеченные пустой цепочкой ε | Из одного состояния выходит несколько переходов, помеченных одним и тем же символом |
---|---|
Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.
В силу последних двух замечаний, несмотря на большую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.
Автоматы и регулярные языки
Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет — так называется множество слов, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.
Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.
См. также
Ссылки
Ссылки
- М. И. Дехтярь Введение в схемы, автоматы и алгоритмы
- Open source генератор конечных автоматов на языке С++ по XML файлам описания
Wikimedia Foundation.2010.
Полезное
Смотреть что такое "Конечные автоматы" в других словарях:
- Конечный автомат — Конечный автомат абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Существуют различные варианты задания конечного автомата. Например,… … Википедия
- НКА — Конечный автомат в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно.… … Википедия
- Эквивалентность детерминированных и недетерминированных конечных автоматов — Конечный автомат в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно.… … Википедия
- АВТОМАТОВ СПОСОБЫ ЗАДАНИЯ — варианты описания автоматов, их функционирования или поведения. А. с. з. зависят от подхода к определению понятия автомата. При макроподходе (см. Автомат конечный).описывается внешнее поведение автомата; при микроподходе задание должно содержать… … Математическая энциклопедия
- Автоматное программирование — Автоматное программирование это парадигма программирования, при использовании которой программа или её фрагмент осмысливается как модель какого либо формального автомата. В зависимости от конкретной задачи в автоматном программировании… … Википедия
- Перебор по словарю — (англ. dictionary attack) атака на систему защиты, использующая метод полного перебора (англ. brute force) предполагаемых паролей, используемых для аутентификации, осуществляемого путем последовательного пересмотра всех слов… … Википедия
- АВТОМАТОВ ПОЛНЫЕ СИСТЕМЫ — специальные подмножества заданного класса Мавтоматов, на к ром определено нек рое множество операций со значениями в М. Эти подмножества обладают следующим основным свойством (свойством полноты): множество всех автоматов, к рые получаются путем… … Математическая энциклопедия
- Трахтенброт, Борис Авраамович — Борис Авраамович Трахтенброт (также Борис Абрамович, англ. Boris (Boaz) Trachtenbrot, Trakhtenbrot, Trajtenbrot Trahtenbrot, ивр. בועז טרכטנברוט; род. 20 февраля 1921, Бричево Сорокского уезда, Бессарабия) советский и израильский… … Википедия
- Борис Авраамович Трахтенброт — (также Борис Абрамович, англ. Boris (Boaz) Trachtenbrot, Trakhtenbrot, Trajtenbrot Trahtenbrot, ивр. בועז טרכטנברוט; род. 20 февраля 1921, Бричево Сорокского уезда, Бессарабия) советский и израильский математик в области математической логики,… … Википедия
- Борис Трахтенброт — Борис Авраамович Трахтенброт (также Борис Абрамович, англ. Boris (Boaz) Trachtenbrot, Trakhtenbrot, Trajtenbrot Trahtenbrot, ивр. בועז טרכטנברוט; род. 20 февраля 1921, Бричево Сорокского уезда, Бессарабия) советский и израильский математик в… … Википедия