2.3. Формальные грамматики и языки

Последовательности символов, поступающих на вход автомата, создаются внешними по отношению к автомату объектом. Такие последовательности несут информацию о состоянии объекта и используются автоматом, например, для управления объектом, т.е. для изменения его состояния.

Входная последовательность может быть получена и другим способом:

Как результат считывания описания некоторого объекта или задачи, представленного на некотором входном языке. В этом случае состояние объекта представляется в виде описания объекта, а абстрактный символ состояния автомата – это условное обозначение класса рассматриваемого состояния (рис. 11).

Рис. 11

На рис. 11 S_1,1, S _1,2, S _1,3, … , S _2,1, S _2,2, S _2,3, … - состояния объекта.

Описание сложного объекта включает перечень компонентов, составляющих объект, и отношения между компонентами. Такие описания имеют вид цепочек над алфавитом V и подчиняются некоторым ограничениям, а именно ограничениям языка описания.

Выбор алфавита, на котором представляется описание, зависит от физических свойств носителя. Например, в вычислительной технике широко используется двоичный алфавит B=[1.0].

Синтаксис языка описания позволяет выявить синтаксические отношения между компонентами описания (буквами, словами, фразами).

Соответствие компонентов описания компонентам реального объекта, а также соответствие синтаксических отношений между компонентами описаний реальным отношениям между компонентами объекта позволяет “вычислить” смысл описания, т.е. определить отношения между компонентами объекта, которые не представлены в явном виде в рассматриваемом описании объекта.

Формальный язык над алфавитом V – это подмножество LV*, где V* - множество всевозможных цепочек над V.

Формальный язык можно задать с помощью формальной порождающей грамматики: G=<w₁,V,W,R>,

Где w₁W – начальный символ, из которого выводятся правильные цепочки над V;

W – множество вспомогательных символов, каждый из которых обозначает некоторый класс правильных цепочек;

R – множество правил ввода.

В соответствии с классификацией Н. Хомского различают бесконечные (контекстно-свободные) и контекстно-зависимые грамматики.

В бесконечных грамматиках каждое правило из R имеет вид:

w::, где wW, (VUW)* .

если имеется несколько правил

w:: ₁, w::₂ , … , w::=2k,

раскрывающих нерминалной символ w, то они могут быть записаны компактно

w:: ₁|₂ | … | _k .

Язык L(G), порождаемый грамматикой G, - это множество терминальных цепочек, т.е. цепочек над V, выводимых с помощью правил грамматики G. Грамматика называется автоматной, или

A-грамматикой, если все правила её имеют вид w::=vw¹ ,

Где wW, vV, w¹WU{w₀}, w₀ – пустой символ.

Например, построим грамматику, порождающую двоичные числа вида 110#, 0.1#, 010.011# и т.д. в двоичном алфавите

V= {0111.1#}.

Символ “.”используется для отделения целой части от дробной части числа, а символ “#” служит как разделитель для обозначения конца записи числа. Для упрощения записи правил введён символ двоичной цифры d{011} и перейти к алфавиту V= {d₁ . d#}.

Рассмотрим грамматику со следующими правилами:

w::=dw

w::= # | dw |.w

w::= # | dw

С использованием пустого символа w₀ правила для w₂ и w₃ можно переписать

w₂ :: = # w₀ | dw₂ |. w₃

w₃ :: = # w₀ | dw₃