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

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

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

Как результат считывания описания некоторого объекта или задачи, представленного на некотором входном языке. В этом случае состояние объекта представляется в виде описания объекта, а абстрактный символ состояния автомата – это условное обозначение класса рассматриваемого состояния (рис. 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₁eW – начальный символ, из которого выводятся правильные цепочки над V;

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

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

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

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

w::h, где weW, he(VUW)*.

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

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

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

w::h ₁|h₂ | … | h_k.

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

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

Где weW, veV, w¹eWU{w₀}, w₀ – пустой символ.

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

V= {0111.1#}.

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

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

w::=dw

w::= # | dw |.w

w::= # | dw

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

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

w₃:: = # w₀ | dw₃

2.4. АВТОМАТЫ И ГРАММАТИКИ [ 7 ]

Автомат распознаёт цепочку h над V, если, находясь в начальном состоянии, автомат получает на вход цепочку h последовательно символ за символом, и после завершения цепочки оказывается в выделенном состоянии w₀. Для построения автомата, распознающего язык, порождаемый А-грамматикой G, необходимо каждому вспомогательному символу weW поставить в соответствие состояние автомата, в качестве множества терминальных символов взять множество входных символов автомата, каждому правилу w::vw¹ поставить в соответствие переход между состояниями w и w¹ под воздействием входного символа v. Начальному состоянию автомата соответствует w₁,а выделенному состоянию w₀.

В рассматриваемом примере построим граф автомата (Рис. 12).

Рис.12

Для “вычисления” смысла цепочки можно ввести выходные символы автомата, вызывающие соответствующие семантические программы.

В рассматриваемом примере это:

У₁) S:=d

У₂) S:=2*S=d

У₃) M:=1

У₄) M:=M/2; S:=S+d*M

У₅) выдача числа S

У₆) сообщение о синтаксической ошибке

Структура автомата, который можно назвать интерпретирующим, приведена на Рис. 13.

Рис. 13

Правила А-грамматики можно записать в виде:

w_i::v_j w_k (jeJ_i, keK_ij, ieI),

причём w_ke WU{ w₀ }, где w₀ – пустой символ.

Если существует | K_ij |>1, то автомат, построенный по грамматике G с помощью изложенной выше процедуры, будет недетерминированным.

Например, системе правил

w₁:: v₁ w₂ | v₂ w₃

w₂:: v₂ | v₂ w₂

w₃:: v₃ | v₃ w₃

соответствует недетерминированный автомат, граф которого показан на рис. 14.

Рис.14

Для построения детерминированного автомата преобразуем недетерминированный автомат путём введения новых состояний и правил на основе следующих соотношений

w₁ :: = v_j { w_k | keK_1j };

{w_i | ieM}:: = v_j { w_k | ke K_ij ,ieM} (ieUJ_i ),

где множество вида { w_t | teT} соответствует новым состояниям.

В рассматриваемом примере получим

J₁ = {1}, J₂ = {2}, J₃ ={3};

K₁₁ ={2,3}, K₂₂ ={0,2}, K₃₃ = {0,3};

w₁ ::=v₁ {w₂ , w₃ }

{w₂ , w₃ }::=v₂ {w₀ , w₂ } | v₃ {w₀ , w₃ };

{w₀ , w₂ }::=v₂ {w₀ , w₂ };

{w₀ , w₃ }::=v₃ {w₀ , w₃ }.

Граф переходов детерминированного автомата показан на Рис. 15

Рис.15

Выделенными состояниями являются {w₀ , w₂ } и {w₀ , w₃ }.

Завершение работы автомата в этих состояниях означает распознование цепочки языка.

В заключении приведён пример бесконтекстной грамматики, не являющейся автоматной. Эта грамматика, распознающая правильные скобочные выражения, имеет правила

w₁::={w₂ , w₃ }; w₂ ::=(w₂) | w₀; w₃ ::=w₂ | w_0,

_где w₁ – начальный символ

w₀ - пустой символ

(,) - терминальные символы.

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

Рис. 16

Состояние является одновременно и начальным и выделенным заключительным состоянием. Распознавание цепочки ((((((((

^{1 2 3 4 5 6 7 8}

показано на рис. 17

Рис. 17

2.5. МАШИНА ТЬЮРИНГА [ 5, 8 ]

Универсальный способ задания алфавитного преобразования – алгоритмический, т.е. основанный на понятии алгоритма [12]. Под алгоритмом обычно понимается точное предписание, определяющее процесс переработки исходных данных в требуемый результат.

При этом требуется: 1) чтобы исходные данные были заданы в конкретном алфавите и могли принимать значения из некоторого множества, т.е. носили массовый характер; 2) чтобы процесс переработки данных состоял из отдельных дискретных шагов и был детерминированным; 3) чтобы были чётко указаны условия остановки процесса и что следует считать результатом процесса.

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

Было предложено несколько точных математических моделей, уточняющих понятие алгоритма, - система рекурсивных функций Клини, машина Тюринга, нормальный алгоритм А.А. Маркова, схема Колмогорова-Успенского, лямбда- конверсии Черча, финитные комбинаторные процессы Поста.

А. Черч впервые обосновал положение о том, что все уточнения понятия алгоритма эквивалентны (“Тезис Чёрча”), т.е. правильно отражают интуитивное представление об алгоритмах, сложившиеся в математике.

Модель алгоритма, называемая машиной Тьюринга, состоит из бесконечной ленты Л, разделенной на ячейки, и читающей – пишущей головки Г, которая перемещается по ленте.

В каждой ячейке может быть записан один символ из алфавита А. Головка может находиться в одном из внутренних состояний, принадлежащих конечному множеству S. Работа машины происходит в дискретном времени. В зависимости от состояния головки seS и символа а eА, против которого она стоит, головка записывает на ленте новый символ а+ (или оставляет старый), переходит в новое состояние s+ (или остается в старом) и передвигается: вправо (R), влево (L) или остается в прежнем положении (N).

В табл. 11 приведен пример команд машины Тьюринга, имеющих вид (а,s) → (a+, D, s+), где а e{_, +, 1}, s e{s1, s2, s3,!}, D e{R, L, N}.

Таблица 11

a	s
s1	s2	s3
_ +	_R s3 _R s1 _N!	1 L s2 _R s1 + Ls2	1 R s3 1 N s2 + R s3

Данная машина выполняет сложение чисел, представленных в унитарном коде. Например, сложение чисел 111+11 (три плюс два) осуществляется за три цикла:

111+11

11+111

1+1111

+11111

Начальное состояние головки s1. Состояние s3 соответствует перемещению головки вправо с «перетаскиванием» единицы. Состояние s2 соответствует перемещению головки влево. Состояние! означает остановку машины. На рис. 18 показан начальный этап вычислений.

Л … _ 11 + 111 _ …

Г s1

Л … _ _ 1 + 111 _ …

Г s3

Л … _ _ 1 + 111 _ …

Г s3

Л … _ _ 1 + 111 _ …

Г s3

Л … _ _ 1 + 111 _ …

Г s3

Л … _ _ 1 + 111 _ …

Г s3

Л … _ _ 1 + 111 _ …

Г s3

Л … _ _ 1+1111 _ …

Г s2

Рис. 18

Дата добавления: 2015-10-23