В коде программы этот символ будет иметь вид « * ». Часто при распознании цепочек возникает ситуация, когда невозможно текущей паре "состояние – входной символ" поставить в соответствие новое состояние. По сути это означает, что цепочка не принадлежит распознаваемому множеству, хотя она и не просмотрена до символа "конец цепочки". Такие ситуации в таблице переходов помечаются символом "error"; попав в такое состояние, КА отвергает проверяемую цепочку и переходит в начальное состояние.
КА всегда начинает работать из начального состояния s0. Символы распознаваемой цепочки поступают посимвольно, начиная с первого, и изменяют состояния КА в соответствии с таблицей переходов. После поступления символа "конец цепочки" достигнутое автоматом состояние фиксируется и сравнивается с множеством допускающих состояний. На основании этого сравнения цепочка допускается или отвергается.
По сути КА работает как фильтр, который пропускает "правильные" цепочки. Другая трактовка КА – компактный алгоритм распознания регулярных, в том числе и бесконечных множеств, который строит программист перед началом кодирования.
Построение КА для распознания заданного множества цепочек – процесс творческий и неоднозначный. Теоретически для распознания одного и того же множества цепочек можно построить бесконечное множество КА. Описанный выше принцип распознания применим далеко не ко всякому регулярному множеству. Он эффективен в следующих случаях:
– распознаваемые цепочки содержат определенные сочетания символов в начале, конце или (и) середине цепочки;
– распознаваемые цепочки содержат ограниченное число повторений определенных символов или их сочетаний (не больше n; точно n; не меньше n, причем n = 1,2,3);
– распознаваемые цепочки содержат запрет на определенные сочетания символов в начале, конце или (и) во всей цепочке;
– распознаваемые цепочки содержат комбинации названных выше ограничений.
1.1.2 Эквивалентные состояния КА
Состояния s и t двух различных конечных автоматов эквивалентны тогда и только тогда, когда первый КА, начав работу из состояния s, будет допускать те же цепочки, что и второй КА, начав работу из состояния t. Если эти состояния начальные, то эти автоматы эквивалентны.
Два состояния конечного автомата эквивалентны тогда и только тогда, когда, начав работу из этих состояний, конечный автомат будет допускать одни и те же цепочки.
Другими словами, если для двух состояний КА нет различающей цепочки, то такие состояния эквивалентны (различающая – такая цепочка символов, которая приводит КА из сравниваемых состояний к различным конечным результатам).
Эквивалентные состояния, принадлежащие одному КА, не нарушая эквивалентности, можно заменить одним (в таблице переходов оставить одну из строк эквивалентных состояний, удалив остальные, при этом заменить имена удаленных состояний на оставленное).
1.1.3 Недостижимые состояния КА
Недостижимыми называются такие состояния КА, которые не могут быть достигнуты из начального состояния воздействием любых входных символов.
Не нарушая эквивалентности, такие состояния можно исключить из таблицы переходов КА. Процедура поиска недостижимых состояний следующая:
Шаг 1: записать одноэлементное множество, в которое входит начальное состояние.
Шаг 2: дополнить это множество состояниями, в которые переходит КА из состояний, уже присутствующих в множестве при воздействии любых входных символов.
Шаг 3: если на шаге 2 множество не пополняется новыми элементами, то получен исчерпывающий список достижимых состояний; остальные состояния КА недостижимы
Конечный автомат, в котором исключены недостижимые и эквивалентные состояния называется минимальным КА.
В расширенном представлении под термином "язык" понимают всякое средство общения, состоящее из:
– знаковой системы, т.е. множества допустимых последовательностей знаков;
– множества смыслов этой системы;
– соответствия между последовательностями знаков и смыслами, делающими осмысленными допустимые последовательности знаков.
Знаками могут быть буквы алфавита, математические обозначения, звуки, ритуальные действия и т.д. Hаука об осмысленных знаковых системах называется семиотикой. Hаиболее исследованными являются знаковые системы, у которых знаками являются символы алфавита. Правила, определяющие множество текстов (допустимых последовательностей знаков), образуют синтаксис языка; описание множества смыслов и соответствия между текстами и смыслами – семантику языка. К таким знаковым системам относятся естественные языки, языки различных областей науки, языки программирования.
Семантика языка существенно зависит от назначения языка, в то время, как для синтаксиса можно сформулировать понятия и методы, не зависящие от назначения и целей языка. Для исследования синтаксиса сложился специальный математический аппарат – теория формальных грамматик, в котором язык понимается уже не как средство общения, а как множество формальных объектов – последовательностей символов алфавита. Эти последовательности называют цепочками и язык понимают как множество цепочек.
Пусть задан алфавит V, в котором можно построить множество V*(читается – итерация алфавита V) цепочек. Формальный язык L в алфавите V – это подмножество цепочек из V* (L Ì V*). Описание формальных языков осуществляется с помощью формальных порождающих грамматик (формальных грамматик).
Формальная порождающая грамматика G (в дальнейшем – грамматика G) – это формальная система, определяемая четверкой объектов:
G[Z] = (VN, VT, Z, P),
где VN - алфавит нетерминалов (вспомогательных символов);
VT – алфавит терминалов (основных символов);
Z – начальный символ (аксиома) грамматики;
P – конечное множество правил.
Hетерминалы принято обозначать большими буквами латинского алфавита, терминалы – малыми буквами. В алфавит нетерминалов обязательно входит начальный символ грамматики.
Каждое правило из множества P имеет вид x - y, – где x, y цепочки, состоящие из терминальных и нетерминальных символов. В дальнейшем будем рассматривать грамматики, содержащие только правила, левые части которых состоят из одного нетерминального символа (контекстно–свободные грамматики). При этом должно быть хотя бы одно правило, левая часть которого – начальный символ грамматики.
Грамматика описывает бесконечный язык, если хотя бы одно из правил рекурсивно, т. е. в правой части содержится его левая часть в явном или неявном виде.
Сентенциальная форма – любая цепочка терминальных и нетерминальных символов, которая получается на любом шаге процесса вывода. Множество сентенциальных форм можно получить из дерева вывода, обходя его по узлам и соблюдая следующие правила:
– начинать обход с самого левого узла;
– обход надо совершать так, чтобы при переходе к следующему узлу образованное поддерево не включало, как элемент, предыдущее поддерево.
Фраза – часть сентенциальной формы, выводимая из одного нетерминала за несколько шагов. Для простой фразы шаг вывода равен 1.
Одну и ту же цепочку можно получить, применяя правила в различных последовательностях (деревья выводов различны). Если для однозначности в процессе вывода на каждом шаге применять правило к самому левому(правому) нетерминалу в сентенциальной форме, то получим левосторонний(правосторонний) вывод.
Таким образом:
– Каждой цепочке выводимой в заданной грамматике соответствует одно или несколько деревьев вывода.
– Каждому дереву соответствует один или больше выводов.
– Каждому дереву соответствует единственный правый и единственный левый выводы.
– Если каждой цепочке, выводимой в данной грамматике, соответствует единственное дерево вывода, то такая грамматика называется однозначной (в правой части каждого правила такой грамматики содержится не более одного нетерминала).
Языком L(G), порождаемым грамматикой G, называется множество всех цепочек в алфавите терминальных символов VT, выводимых из начального символа грамматики.
1.2.2 Классификация грамматик
Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик (рисунок 1):
| 0-й тип | Правила имеют вид: x - y, где x и y – любые цепочки терминалов и нетерминалов | ||
| С фразовой структурой. | 1-й тип | Правила имеют вид x - y, где | x | <= | y | (правая цепочка не короче левой). | |
| контекстно–зависимые (КЗ) | 2-й тип | вид правил A - y, где A – нетерминал, y – любая цепочка | |
| контекстно–свободные (КС) | 3-й тип – автоматные грамматики (вид правил A - aB или A - b или A-e где a,b–терминалы; A,B–нетерминалы;e-пустая цеп). | ||
Рисунок 1 – Классификация грамматик
Каждый тип грамматик включает грамматики более высоких типов, как частные случаи.
Для построения распознавателей грамматик, других целей очень часто необходимо преобразовать правила исходной грамматики к соответствующему виду. При этих преобразованиях язык, порождаемый исходной и полученными после преобразования грамматиками не должен меняться.
1.2.3 Эквивалентные преобразования грамматик
Для построения распознавателей грамматик, других целей часто необходимо преобразовывать правила исходной грамматики к соответствующему виду. При этом язык, порождаемый исходной и полученными после преобразования грамматиками, не должен меняться.
Две грамматики эквивалентны, если они порождают один и тот же язык(одни и те же цепочки терминальных символов).Рассмотрим ряд процедур, которые всегда приводят к эквивалентным преобразованиям.