Конечные автоматы (КА) и автоматные языки

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

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

Регулярные выражения — это формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов.

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

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

Если, прочитав входную цепочку, автомат оказывается в некотором конечном состоянии из множества F(конечных состояний), то говорят, что он принял ее. Множество цепочек, принимаемых конечным автоматом, называется языком, распознаваемым данным конечным автоматом.

Автоматы A и B называются эквивалентными, если совпадают распознаваемые ими языки, т.е. L_A = L_B

Данное словесное описания конечного автомата и его работы может быть заменено следующим формальным определением. (с79)

(с 80)