Раздел 5. Конечноавтоматные преобразователи, автоматные языки и грамматики.
Конечный автомат можно рассматривать не только как дискретный преобразователь информации, реагирующий на отдельные комбинации входных сигналов, но и как устройство, способное распознавать и некоторым образом классифицировать такие последовательности. Поставиви в соответствие комбинациям входных и выходных сигналов множество некоторых символов (входные и выходные множества могут не совпадать), можно утверждать, что конечный автомат выполняет алгоритмические операции над комбинациями входного множества символов. Последовательности символов часто называют словами (цепочками), а множество слов – языком. Таким образом, конечный автомат можно рассматривать как устройство выполняющее алгоритмические операции над языками. Такие языки называют формальными.
Конечный автомат может, например, преобразовывать входные последовательности цепочек в некоторую выходную последовательность. Такая операция называется трансляцией со входного языка в выходной (в программу). В этом смысле конечный автомат может быть использован, например, в лексическом анализаторе компилятора, отвечающего за разбиение текста на логические единицы, такие как идентификаторы, ключевые слова, знки препинания и т. д.
Для дальнейшего изложения теории конечных автоматов и теории формальных языков, введем дополнительные понятия и определения.
Алфавиты, цепочки, языки.
Определение. Под алфавитом (словарем) понимается произвольное конечное непустое конечное множество V={a1,a2,…,an}, элементы которого называют символами или буквами.
Наиболее часто используются следующие алфавиты:
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 будем обозначать Lv, или просто L, если V очевиден.
Несмотря на то, что алфавит V конечен, множество цепочек V*, в общем случае, представляет собой бесконечное счетное множество. Так как язык Lv есть подмножество бесконечного счетного множества V*, то и языков бесконечное число. Говорят, что это множество мощности континиум. Единственное существенное ограничение для множеств, которые могут быть языками, состоит в требовании, чтобы все алфавиты были конечными. Таким образом, хотя языки и могут содержать бесконечное количество цепочек, но эти цепочки должны быть составлены из некоторого фиксированного конечного алфавита.
Примеры.
1. V1={0,1}; L1 – множество двоичных чисел. Следовательно, 101 L1; 10011 L1.
2. V2={x,y,z}; L2={xyz,yz}; Тогда xyz L2, yz V2, x V2, xy V2.
3. V3={a,b,c}, L3={anbcn|n>0}. Тогда aabcc L3, abccc L3, abbc L3.
4. V4={быстродействующий, компактный, … , считает, печатает, … , запоминает, управляет, …}, L4 - русский язык.