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

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

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

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

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

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

Автомат

Автомат в последовательность (кортеж) из пяти элементов $(Q, \Sigma, \delta, S_0, F)$ , где:

$Q$ в множество состояний автомата
$\Sigma$ в алфавит языка, который понимает автомат
$\delta$ в функция перехода, такая что $\delta : Q \times \Sigma \rightarrow Q$
$S_0$ в начальное состояние
$F$ в множество состояний, называемых «принимающие состояния».

Слово: Автомат читает конечную строку символов a₁,a₂,в., a_n , где a_i в€€ Σ, и называется словом.Набор всех слов записывается как Σ*.

Принимаемое слово: Слово w в€€ Σ* принимается автоматом, если q_n в€€ F.

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

$L= \{ w \in \Sigma^{\star}|\hat\delta(S_0,w)\in F\}$

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

[править] Применение

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

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

[править] Типовые задачи

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

[править] См. также

[править] Литература

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. в М.: Вильямс, 2002. в С. 528. в ISBN 0-201-44124-1
Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. в Новосибирск: НГУ, 1995. в C. 112.

[править] Ссылки

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

Содержание

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

[править] Применение

[править] Типовые задачи

[править] См. также

[править] Литература

[править] Ссылки

Личные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Участие

Печать/экспорт

Инструменты

На других языках