Порождение и распознавание цепочек.

Конечный автомат (автомат Мили)S=<V_a,Q,V_b,q₀,F,G>, где

V_a={a₁,a₂,…a_m},m1 – входной алфавит автомата,

V_b= {b₁,b₂, …,b_n},n1 – выходной алфавит автомата,

Q= {q₀,q₁,…q_k},k0 – внутренний алфавит (алфавит состояний),

q₀Q– начальное состояние автомата,

F- функция переходов;F:QV_aQ,

G- функция выходов,G:QV_aV_b.

Автомат однозначно задает отображение V_a*V_b* (входной цепочки в выходную).

Пример автомата:

Пусть V_a=V_b= {a,b},Q= {A,B},q₀=A. Функции переходов и выходов могут быть заданы в функциональной форме:

F(A, a) = A	G(A, a) = a
F(A, b) = B	G(A, b) = a
F(B, a) = A	G(B, a) = b
F(B, b) = B	G(B, b) = b

Либо в виде объединенной таблицы входов-выходов, в которой по столбцам указаны исходные состояния, во строкам – входы, в соответствующей ячейке через запятую указываются состояние, в которое переходит автомат и соответствующий выходной сигнал.

	A	B
a	A, a	A, b
b	B, a	B, b

Диаграмма (граф переходов автомата), представляющая этот автомат, изображена на рис. 3.

Рис. 3

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

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

Лингвистический автомат– этоS_L= <Q,V_T,q₀,F,K>,

где Q= {q₀,q₁,…q_k},k0 – множество состояний автомата (внутренний алфавит),

V_T ={a₁,a₂,…a_m},m1– множество терминальных символов (внешний алфавит) автомата,

q₀ – начальное состояние автомата,q₀ Q,

F:QV_TQфункция переходов,

KQ– множество конечных(заключительных) состояний.

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

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

На каждом шаге обозревается ровно один символ. Пара (q,a), гдеa- обозреваемый символ, аq- состояние автомата, называется ситуацией автомата. Если автомат находится в ситуации(q_i,a_j) и F(q_i, a_j)=q_k, то считывающая головка перемещается на один символ вправо, автомат переходит в состояниеq_k. Получаемая ситуация(q_i,a_j+1) (обозревается следующий символ на ленте. Если жеF(q_i, a_j) не определена, то входная цепочка не допускается автоматом.

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

Более строго:

В начале работы автомат находится в состоянии q₀, на входе – цепочкаa₁,a₂,…,a_n, обозревается самый левый символ цепочки ситуация (q₀,a₁) , затем переход в некоторую ситуацию (q_i,a₁),…, (q_j,a_n), и, наконец, в ситуацию (q_s,) &q_sK. Назовём конфигурацией автомата паруH=(q,x), гдеq—текущее состояние автомата;x—остаток входной цепочки, самый левый символ которой обозревается входной го­ловкой. Конфигурация, очевидно, определяет и ситуацию. Говорят, что конфигурация (p,x₁) получена из конфигурации (q,x) за один такт (обозначается (q,x)├(p,x₁) ), еслиx=ax₁иF(q,a)= p.

. Если H₀,H₁,…,H_n(n1) - последовательность конфигураций, таких, чтоH_i ├H_i+1 ,i{1,…,n}, то, как и раньше, будем использовать обозначенияH₀ ├⁺H_n илиH₀ ├*H_n если справедливоH₀ ├⁺H_n H₀=H_n.

Пусть x— анализируемая цепочка. Начальная конфигу­рация имеет вид (q₀,x) заключительная – (q_s,),q_sF. Говорят, что автомат A допустил цепочкуx, если (q₀,x)├* (q,) иqF(Использование отношения├* позволяет включить в множество допускаемых цепочек и пустую цепочку, еслиq₀F.

Языком L(A), допускаемым конечным автоматомA, называется множество допускаемых им цепочек

L(A) = { x / (q₀, x) ├ * (q, ) & q K}.

Диаграмма лингвистического автомата отличается от диаграммы автомата Мили выделением конечных состояний и отсутствием выходов.

Например, для лингвистического автомата S_A= <Q, {a,b,c},q₀,F, {q₁}>, функция переходов которого

F(q₀,c)=q₀,

F(q₀,a)=q₁,

F(q₁, b)= q₁,

диаграмма представлена на рис. 4.

Рис.4

Язык, распознаваемый этим автоматом L(S_A)= {cⁿab^m,n,m0}.

Цепочка не распознается автоматом, если или нет перехода по читаемому символу, или в результате прочтения цепочки состояние, в которое перешел автомат - не конечное.

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

Граф автомата в силу тождественности его структуры с диаграммой грамматик всегда может рассматриваться как диаграмма некоторой грамматики, роль нетерминальных символов в которой будут играть метки состояний автомата. Нетрудно видеть, что грамматика, полученная по графу переходов автомата, при интерпретации последнего как ее диаграммы будет порождать тот же самый язык, который допускается автоматом. В обоих случаях язык однозначно определяется множеством путей из начальной вершины в заключительные, а множество путей совпадает, так как граф один и тот же. Таким образом, по любому конечному автомату может быть построена эквивалентная А-грамматика и, следовательно, абстрактно взятый ориентированный граф с помеченными вершинами и дугами, в котором выделена начальная и множество заключительных вершин и удовлетворяются требования однозначности отображения F, может рассматриваться и как диаграмма грамматики и как граф переходов автомата - все дело в интерпретации.

По диаграмме автомата всегда легко построить эквивалентную грамматику (автомат по грамматике строить сложнее, так как в грамматике одному символу входного алфавита может соответствовать более одного перехода см., например, рис. 2.

Правила грамматики по диаграмме автомата строится следующим образом:

Каждому состоянию автомата сопоставляем нетерминал грамматики.

Каждому переходу, соответствующему из состояния Pпо терминалуaв состояниеQсопоставляется правило грамматикиPaQ.

Каждому конечному состоянию Rсопоставляется правилоR.

Начальному состоянию автомата сопоставляется начальный символ грамматики.

Например, автомату, диаграмма которого представлена на рис.4, соответствует грамматика G₁₀ с правилами

S cS a A

A b A

где состоянию q₀сопоставлен нетерминалS, а состояниюq₁- нетерминалA.

Таким образом, состояния конечного автомата однозначно отображаются в нетерминалы грамматики.

Однако, если мы рассмотрим грамматику G₁₁ cправилами

S a S a A

A b Ab K

K,

диаграмма которой представлена на рис. 5

Рис.5

Однозначность нарушается неоднозначностью переходов, допускаемых в грамматиках.