Раздел 5. Конечноавтоматные преобразователи, автоматные языки и грамматики.

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

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

Для дальнейшего изложения теории конечных автоматов и теории формальных языков, введем дополнительные понятия и определения.

Алфавиты, цепочки, языки.

Определение. Под алфавитом (словарем) понимается произвольное конечное непустое конечное множество V={a₁,a₂,…,a_n}, элементы которого называют символами или буквами.

Наиболее часто используются следующие алфавиты:

1. Множество строчных букв русского алфавита V={а,б,…,я};

2. Множество строчных букв латинского алфавита V={a,b,…,z};

3. Десятичный алфавит V={0,1,…,9};

4. Двоичный или бинарный алфавит V={0,1}.

Определение. Словом или цепочкой в алфавите V называют конечную упорядоченную последовательность символов этого алфавита V*. Символы в цепочке могут повторяться. Например, цепочка символов V* из алфавита V={0,1}, может выглядеть следующим образом V*={011001}.

Для удобства, аналогично пустому множеству, вводится пустая цепочка ε. Эта цепочка не содержит ни одного символа. Ее можно рассматривать как цепочку в любом алфавите. Если цепочка содержит n символов из слов алфавита V (считаются все символы цепочки, независимо от их повторения), то говорят, что цепочка имеет длину n. Таким образом, пустая цепочка ε имеет длину 0. Длину цепочек принято обозначать |V*| и, следовательно, для пустой цепочки | ε*|=0.

Пусть x и y цепочки в некотором алфавите V. Тогда под xy понимается операция конкатенации (соединение), т.е. в результате этой операции получаем новую цепочку, в которой последовательно записаны цепочки x и y.

Из определения операции конкатенации следует, что если x V* и y V*, то

xy V*. Конкатенация любой цепочки с пустой цепочкой равна самой цепочке εx=xε=x.

Отметим, что операция конкетенации является ассоциативной операцией x(yz)=(xy)z, но не является коммутативной операцией, поскольку, вообще говоря, xy≠yx.

Если цепочка z V* имеет вид xy V*, то цепочку x называют префиксом цепочки z, а цепочку y – суффиксом цепочки z. Например, если z=10011, то, по определению, префиксами цепочки z являются: пустая цепочка ε, цепочка 1, цепочка 10, цепочка 100, цепочка 1001 и, наконец, сама цепочка z=10011. Аналогично, суффиксом цепочки z может быть любая из следующих цепочек: ε, 1, 11, 011, 0011, z.

Определение. Произвольное подмножество множества цепочек V* называется языком.

Язык над алфавитом V будем обозначать L_v, или просто L, если V очевиден.

Несмотря на то, что алфавит V конечен, множество цепочек V*, в общем случае, представляет собой бесконечное счетное множество. Так как язык L_v есть подмножество бесконечного счетного множества V*, то и языков бесконечное число. Говорят, что это множество мощности континиум. Единственное существенное ограничение для множеств, которые могут быть языками, состоит в требовании, чтобы все алфавиты были конечными. Таким образом, хотя языки и могут содержать бесконечное количество цепочек, но эти цепочки должны быть составлены из некоторого фиксированного конечного алфавита.

Примеры.

1. V₁={0,1}; L₁ – множество двоичных чисел. Следовательно, 101 L₁; 10011 L₁.

2. V₂={x,y,z}; L₂={xyz,yz}; Тогда xyz L₂, yz V₂, x V₂, xy V₂.

3. V₃={a,b,c}, L₃={aⁿbcⁿ|n>0}. Тогда aabcc L₃, abccc L₃, abbc L₃.

4. V₄={быстродействующий, компактный, …, считает, печатает, …, запоминает, управляет, …}, L₄ - русский язык.