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

Материал из Википедии — свободной энциклопедии

В дискретной математике, разделе информатики, теория автоматов изучает абстрактные машины в виде математических моделей, и проблемы, которые они могут решать. Теория автоматов наиболее тесно связана с теорией алгоритмов. Это объясняется тем, что автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результирующую информацию по шагам заданного алгоритма. Эти преобразования возможны с помощью технических и/или программных средств. Автомат можно представить как некоторое устройство (чёрный ящик), на которое подаются входные сигналы и снимаются выходные и которое может иметь некоторые внутренние состояния. При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют число состояний автомата для работы по заданному алгоритму. Такой автомат называют абстрактным. При синтезе автоматов формируют систему из элементарных автоматов, эквивалентную заданному абстрактному автомату. Такой автомат называется структурным.

Слова входного языка можно представить символами множества , который называют входным алфавитом, а слова выходного языка - символами множества , который называют выходным алфавитом.

Множество состояний автомата называют алфавитом состояний.

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

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

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

Есть несколько классов автоматов, например конечные автоматы (различнают детерминированные и недетерминированные конечные автоматы), клеточные автоматы (игра «жизнь»), машины Тьюринга.

[править] Формальное описание

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

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

Автомат — последовательность (кортеж) из пяти элементов (Q,Σ,δ,S₀,F), где:

• Q — конечное множество состояний автомата
• Σ — алфавит языка, который понимает автомат
• δ — функция перехода, такая что
• S₀ — начальное состояние, состояние когда автомат еще не прочитал ни одного символа
• F — множество состояний, называемое «конечные состояния».

Можно утверждать, что язык L, который читается автоматом M, состоит из множества слов w на базе алфавита Σ, так что если эти слова вводятся в M, он приходит в одно из состояний F:

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

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

• Лемма о накачке

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

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