Теория языков программирования и методы трансляции

Уменьшить i на единицу. Если i=0, то алгоритм завершен.

Взять найденное решение для X_i=_iX_i+_i, где _i=_ii, _i=_i0+_{i i+1} X_i+1+…+_{i n} X_n и подставить в него найденные окончательные решения для переменных X_i+1,…, X_n. Получим окончательное решение для X_i. Вернуться к шагу 5.

Система уравнений с регулярными коэффициентами всегда имеет решение, но оно не всегда единственно. Рассмотренный алгоритм всегда находит решение, которое является наименьшей неподвижной точкой системы уравнений.

2.2 Конечные автоматы и грамматики

Леволинейные автоматные грамматики G(VT, VN, P, S) могут иметь правила двух видов: A Bt или A t, где A, BVN, tVT.

Праволинейные автоматные грамматики могут тоже иметь правила двух видов: A tB или A t, где A,BVN, tVT.

Как следует из приведенных правил, автоматные грамматики отличаются тем, что в их правилах вместо цепочки терминальных символов присутствует только один терминальный символ. Очевидно, что любая автоматная грамматика является регулярной, обратное же справедливо не всегда.

Классы обычных регулярных грамматик и автоматных почти эквивалентны (т.е. с точностью до правила S ). В автоматных грамматиках разрешается правило вида S , где S - целевой символ грамматики. При этом символ S не должен встречаться в правых частях других правил грамматики; тогда язык, задаваемый автоматной грамматикой G, будет включать в себя пустую цепочку: L(G).

Существует алгоритм, позволяющий преобразовать регулярную грамматику к автоматному виду. Он очень полезен, т.к. упрощает задачу построения распознавателей для регулярных языков. Кратко его идея состоит в том, что при наличии в правой части правила регулярной грамматики цепочки терминальных символов длины n необходимо ввести n-1 дополнительный нетерминальный символ и записать для каждого из них соответствующие правила, т.е. разбить стоящую справа терминальную цепочку на символы и разнести их по разным правилам.

2.2.2 Определение конечного автомата

Конечным автоматом (КА) называют пятерку следующего вида: M(Q,V,,q₀,F), где

Q - конечное множество состояний УУ автомата;

V - алфавит автомата (конечное множество допустимых символов);

- функция переходов, отображающая Q({V}) в множество подмножеств множества Q: (q,a)=R, aV, qQ, RQ;

q₀ - начальное состояние автомата: q₀Q;

F - множество конечных состояний автомата: FQ, F.

КА называется полностью определенным, если в каждом его состоянии существует функция переходов для всех возможных входных символов: aV, qQ (q,a)=R, RQ.

Работа автомата представляет собой последовательность тактов (или шагов). На каждом шаге работы автомат может остаться в том же состоянии или перейти в другое. Поведение автомата на каждом такте определяется функцией переходов, которая зависит от текущего состояния и входного символа. Если функция переходов допускает несколько переходов в следующее состояние, то КА может перейти в любое из них. В начале работы автомат находится в начальном состоянии q₀. Работа автомата продолжается до тех пор, пока на его вход поступают символы входной цепочки.

Мгновенным описанием (МО), или конфигурацией автомата M называется пара (q, w), где qQ - состояние УУ, wV^* - неиспользованная часть входной цепочки (т.е. символ, обозреваемый считывающей головкой и все символы справа от него). Тогда пара (q₀, w) называется начальной конфигурацией для цепочки w, а конфигурация (q, ) является заключительной, или допускающей, если qF.

Представим такт автомата M бинарным отношением +-_M на множестве конфигураций. Тогда: если (q,a) содержит q' - q'(q,a), то (q,aw)+-_M (q',w) для всех wV^*. Здесь a{V}, т.е. a является символом входного алфавита или пустым символом. Если a, то на таком такте входная головка сдвигается вправо на одну ячейку. Если же a=, то это означает, что состояние автомата изменяется независимо от обозреваемого входного символа.

Рефлексивное и транзитивное замыкание отношения +- обозначается через +-*.

Цепочка w допускается автоматом M, если (q₀,w)+-*(q,) для некоторого qF, т.е. получив на вход эту цепочку, автомат из начальной конфигурации может перейти в заключительную.

Язык, допускаемый (определяемый) автоматом M, представляет собой множество L(M)={wwV^* и qF(q₀,w)+-*(q,)}. Два автомата эквивалентны, если они задают один и тот же язык.

Таким образом, из вышесказанного следует, что КА является распознавателем для формальных языков. Можно доказать, что он является распознавателем именно для регулярных языков.

Пусть M - конечный автомат. Он является детерминированным (ДКА) если множество (q,a) содержит не более одного состояния aV, qQ. Если (q,a) всегда содержит ровно одно состояние, то M является полностью определенным (ПО).

Функция переходов КА может быть задана таблицей или графом переходов (диаграммой). Граф переходов КА - это направленный помеченный граф, вершины которого обозначены состояниями автомата, а дуги - символами входного алфавита. При этом дуга (p,q)p,qQ обозначена символом aV, если в КА определена (p,a) и q(p,a). Начальное и конечное состояния на графе помечаются специальным образом, например, начальное - дополнительной пунктирной линией, а конечное - двойным кружком.

Для моделирования работы КА удобно, чтобы в нем были заданы все возможные переходы для всех символов входного алфавита. Если это не так, то автомат можно привести к полностью определенному виду путем ввода дополнительного состояния «ошибка», на которое замкнуть все неопределенные переходы, а все переходы из этого нового состояния замкнуть на него же.

Рассмотрим 2 примера конечных автоматов - ДКА и НКА.

1. Пусть M=({p,q,r},{0,1},,p,{r}) - ДКА, где функция переходов задана таблицей:

Рассмотрим последовательность тактов для данной цепочки w.

(p,01001) +- (q,1001) +- (p,001) +- (q,01) +- (r,1) +- (r,).

Поскольку rF, это означает, что `01001'L(M).

2. Построим НКА, допускающий цепочки в алфавите {1,2,3}, у которых последний символ цепочки уже появлялся в ней ранее (т.е. цепочка `1232' должна быть допущена, а `122113' - нет). Введем состояния: q₀ - нейтральное, q_i делает предположение, что последний символ цепочки совпадает с индексом состояния, q_f - заключительное состояние. Из состояния q₀ автомат может перейти в q_a, если наблюдает символ ”a”, или остаться в q₀. Находясь в q_a и наблюдая символ ”a”, автомат может перейти в заключительное состояние q_f или остаться в q_a. Из q_f автомат никуда не переходит.

Формально такой автомат определим следующим образом:

M=({q₀,q₁,q₂,q₃,q_f},{1,2,3},,q₀,{q_f}), функция переходов задана таблицей:

Поскольку (q₀,12321)+-*(q_f,), то `12321'L(M).

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

В качестве состояний нового ДКА рассматриваются все состояния исходного автомата, а также всевозможные сочетания этих состояний по два, по три, …, по n, если в исходном автомате было n состояний.

Для всех новых состояний строится функция переходов, в которой для каждого состояния q_iq_j появляется переход в новое состояние, представляющий собой объединение всех существовавших ранее переходов из q_i и q_j.

Начальное состояние нового автомата совпадает с начальным состоянием исходного, а множество конечных состояний нового автомата будут состоять из всех сочетаний, в которых присутствовало q_f - конечное состояние исходного автомата.

После построения ДКА из него удаляют все недостижимые состояния (т.е. состояния, переход в которые невозможен ни при какой входной цепочке).

Доказано, что описанный алгоритм строит ДКА, эквивалентный заданному КА. При этом если исходный автомат имел n состояний, то в наихудшем случае построенный ДКА будет иметь (2ⁿ-1) состояний.

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

Пусть q₁ и q₂ - состояния автомата M, на вход подается цепочка символов w длины k0: wV^*, wk, (q₁,w) +-* (q₃,), (q₂,w) +-* (q₄,). Если при этом одно из состояний (q₃ или q₄) входит в F, а другое - нет, то говорят, что цепочка w различает состояния q₁ и q₂. Если же для любой входной цепочки w длины k она не различает состояния q₁ и q₂, то говорят, что они являются k-эквивалентными или k-неразличимыми. Множество K-эквивалентных состояний составляет класс эквивалентности R(k).

Очевидно, что множества F и Q\F являются 0-эквивалентными, записывается этот факт следующим образом: R(0)={F,Q\F}.

Для построения минимального автомата строятся классы эквивалентности R(n). Алгоритм построения классов эквивалентности:

1. Полагаем n:=0, строится R(0)= {F,Q\F}.

2. n:=n+1. Строится R(n) на основании R(n-1): в класс эквивалентности на шаге n входят те состояния, которые по одинаковым символам переходят в n-1-эквивалентные состояния: R(n):={r_ij(n): {q_ijQ: aV (q_ij,a) r_j(n-1)} i,jN}.

3. Если R(n)= R(n-1), то работа заканчивается. Иначе переход на шаг 2.

Алгоритм минимизации автомата:

Исключить все недостижимые состояния.

Построить классы эквивалентности.

Каждый из этих классов становится состоянием нового автомата.

Функция переходов строится на основании функции переходов исходного автомата и новых состояний.

2.3 Особенности регулярных языков