Пред. страница   . След. страница   Раздел   Содержание

---

2.2. Недетерминированные распознаватели

При построении распознавателей по заданной автоматной грамматике могут получаться распознаватели, у которых имеются несколько переходов из одного состояния под действием одного и того же символа в разные состояния. Такие распознаватели называют недетерминированными распознавателями (НР). Рассмотрение свойств таких распознавателей и их возможностей начнём с формального определения НР.

А'={P',S',s₀' , φ', F'},

где P '-входной алфавит,

S '-алфавит состояний,

s₀' -начальное состояние распознавателя, s₀' Î S',

φ' -функция переходов, которая задаёт отображение:

φ': P'xS' ® M(S'), где M(S') -множество всех подмножеств множества S',

F'-подмножество состояний S', называемых конечными.

Приведённое определение говорит о том, что А' является НР, если множество φ' (s',p) содержит более одного состояния для какого-либо s' Î S' и p Î P'.

Примером такого распознавателя является распознаватель А₃, изображенный на рис. 2.4. Если распознаватель находится в состоянии I, то при считывании входного символа a он может либо остаться в состоянии I, либо перейти в состояние В. Аналогичная ситуация возникает и в состоянии В при считывании входного символа b.

Работу НР можно представить в виде последовательности сменяющих друг друга конфигураций. Однако при переходе к следующей конфигурации может оказаться, что множество φ'(s',p) имеет несколько значений. В этом случае заранее нельзя сказать, какое значение функции переходов нужно выбрать, чтобы достигнуть конечной конфигурации. Можно сделать такой выбор, который приведёт нас к тупиковой ситуации, для которой φ' не определена.

Например, цепочка a a b a b может вызывать следующие смены конфигураций НР A₅, заданного диаграммой переходов, показанной на рис. 2.6.

Рис. 2.6. Диаграмма переходов распознавателя А₅

Рассмотрим работу этого распознавателя при чтении цепочки a a b a b. Если выбрать последовательность переходов, определяемую значениями функции переходов φ'(I,a) = C, φ'(C,a) =B, то получим последовательность конфигураций:

(<I>, a a b a b)|-- (<C>, a b a b)|-- (<B>, b a b )|-- тупик,

которая приводит нас к тупику, поскольку значение функции переходов φ'(B,b) не определено.

При выборе последовательности значений функции переходов φ'(I,a) =I, φ'(I,b) =B, φ'(B,a) =C, φ'(C,b) =B получаем следующий ряд конфигураций:

|-- (<I>, a b a b)|-- (<I>, b a b)|-- (<B>, a b)|-- (<C>,b)|-- (<B>,$),

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

Определение. Цепочка допускается НР, если существует последовательность конфигураций, которая, отправляясь из начальной конфигурации, позволяет получить одну из конечных конфигураций.

Из приведенного определения следует, что для установления факта того, что входная цепочка допускается НР, необходимо доказать существование последовательности конфигураций. Такое доказательство можно выполнить путем просмотра всех возможных последовательностей конфигураций, который может быть связан со значительным объёмом работы. Следствием отмеченного обстоятельства является то, что НР для практических применений предпочитают не использовать.

В общем случае каждое множество j'(s',p) может содержать несколько элементов, и работу НР можно представить в виде переходов между такими множествами. Это обстоятельство является предпосылкой для следующего утверждения.

Утверждение. Если L(А') - язык, допускаемый недетерминированным распознавателем А', то существует детерминированный распознаватель А, допускающий то же множество входных слов L(А)=L(А').

Доказательство этого утверждения выполним путем указания способа построения детерминированного распознавателя.

Для того, чтобы построить детерминированный распознаватель A={P, S, s₀, j, F} по заданному НР A'={ P', S', s₀', j', F'}, воспользуемся следующим планом. Вначале представим состояния заданного НР в виде совокупности подмножеств состояний и переходов между ними. Число подмножеств заданного множества S является конечным , и переходы между такими подмножествами оказываются однозначными. Затем по полученному представлению НР с однозначными переходами построим искомый распознаватель А.

Построение подмножеств состояний НР между которыми осуществляются переходы, выполним следующим образом.

Если S' -множество состояний, S'=s₁', s₂',...,s_m', то каждому состоянию s_i' Î S' поставим в соответствие подмножество S_i" таких состояний, в которые переходит распознаватель из состояния s_i' под действием символа p: j (s_i',p). Естественно, что каждое такое подмножество S_i" ÎM(S').

Пусть S_i"=s_i1', s_i2', ...,s_iq'.

Для каждого состояния s_ik', входящего в S_i", построим множество состояний, в которые переходит распознаватель под действием входного символа p, и обозначим такие подмножества S_i1",S_i2",...,S_iq". Обозначив S_l" объединение этих подмножеств

!!( от t=1 до q)

S_l" = È S_it",

получим подмножество состояний, в которые осуществляется переход из состояний подмножества S_i". Очевидно, что S_l" принадлежит множеству M(S).

Построенные подмножества определяют функцию переходов следующим образом.

j"(S_i",p)=S_l".

Каждому значению построенной функции переходов j"(S_i",p) соответствует одно подмножество S_l", которое включает все состояния, в которые заданный НР совершает переходы из состояний подмножества S_i" под действием символа p.

Таким образом, каждому переходу заданного НР между состояниями s_i' и s_j' под действием символа p соответствует переход между подмножествами, которые содержат эти состояния распознавателя.

Чтобы закончить построение искомого детерминированного распознавателя А, поставим в соответствие каждому подмножеству состояний НР S_j" состояние распознавателя А. Для обозначения состояний условимся использовать имена подмножеств, заключённые в квадратные скобки. Таким образом подмножеству состояний S_j" должно соответствовать состояние искомого распознавателя [s_j"].

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

Если в НР имеет место переход между подмножествами S_k" и S_j", который определяется функцией j'(S_k",p_i)=S_j",то в искомом распознавателе А этому переходу поставим в соответствие функцию вида j([s_k"],p_i)=[s_j"].Подводя итог приведённым выше рассуждениям, опишем порядок построения детерминированного распознавателя А по заданному НР А'.

(1) Учитывая, что распознаватели А и А' должны воспринимать одни и те же цепочки, примем P=P' .

(2) Построим M(S') - множество всех подмножеств S'. Элементами M(S') являются подмножества состояний S_j" = {s₁',s₂',..., s_k'}. В множестве M(S') выберем подмножества, соответствующие переходам заданного распознавателя А'. Каждому такому подмножеству S_j" поставим в соответствие состояние искомого распознавателя , которое обозначим s_j" = [s₁',s₂',...,s_k'] или s_j" = [ S_j" ].

(3) В качестве начального состояния искомого распознавателя примем начальное состояние А': s₀=s₀'.

(4) В множество конечных состояний распознавателя А должны войти все состояния, соответствующие подмножествам S_k", таким которые содержат конечные состояния s_q' из множества F' заданного распознавателя A'.

F = {[S_k'] | S_k' Î M(S₀) & s_q' Î S_k & 's_q' Î F'}

(5) Функцию переходов построим исходя из соответствия переходов между подмножествами НР и состояниями искомого распознавателя. Если после построения подмножеств имеем j"(s_j",p)=S_k", то для искомого распознавателя определим значение функции переходов следующим образом: j([S_j"],p)=[S_k"]. Выполняя эту операцию для всех подмножеств s_j", принадлежащих M(s'), найдём все значения функции переходов А.

Следуя приведённой последовательности действий, построим детерминированный распознаватель для недетерминированного распознавателя А₆, приведенного на рис. 2.7

Рис. 2.7. Диаграмма переходов НР А₆

Множество состояний этого распознавателя состоит из трёх элементов S=[I,A,Z], из которых могут быть образованы 8 различных подмножеств. Используя для обозначения подмножеств цепочки из имён состояний, а для обозначения пустого подмножества символ i, имеем M(S)= [i, I, A, Z, IA, IZ, AZ, IAZ].

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

j(I,a)=IA

j (I,b)= i

j (A,a)= i

j (A,b)=AZ

j (Z,a)= i

j (Z,b)= i

j (IA,a)=IA

j (IA,b)=AZ

j (IZ,a)=IA

j (IZ,b)= i

j(AZ,a)= i

j(AZ,b)=AZ

j(IAZ,a)=IA

j(IAZ,b)=AZ

Эта функция переходов задает распознаватель А_7, диаграмма переходов которого изображена на рис. 2.8.

Рис. 2.8. Диаграмма переходов распознавателя А₇.

Исключая из диаграммы состояния Z, A, IZ, IZA, в которые нет переходов, получаем распознаватель А₇ с тремя состояниями, имеющий следующую таблицу переходов.

Таблица 2.2. Таблица переходов распознавателя А₇.

	a	b
I	|IA	-
IA	IA	AZ
AZ	-	AZ

В качестве второго примера рассмотрим построение распознавателя для недетерминированного распознавателя А₈, заданного диаграммой переходов, приведенной на рис. 2.9.

Рис. 2.9. Диаграмма переходов НР А₈

Функция переходов искомого распознавателя A₉ имеет вид:

j(I,a)=BC

j (I, b)=B

j (B, a)= i

j (B, b)=IC

j (C, a)=B

j (C, b)=I

j (IB, a)=BC

j (IB, b)=IBC

j (IC, a)=BC

j (IC, b)=IB

j (BC, a)=B

j (BC, b)=IC

j (IBC, a)=BC

j (IBC, b)=IBC

Исключая недостижимые состояния, получаем таблицу переходов распознавателя А₉ в следующем виде:

Таблица 2.4. Таблица переходов распознавателя А₉

	a	b
I	BC	B
B	-	IC
IC	BC	IB
IB	BC	IBC
BC	B	IC
IBC	BC	IBC

Способ построения, использованный при решении примеров, оказывается весьма трудоёмким, особенно для распознавателей с большим числом состояний. На практике построение распознавателя по заданному НР выполняется способом последовательного расширения таблицы переходов. Построение таблицы переходов искомого распознавателя осуществляется следующим образом:

а) Вначале заносятся в таблицу все состояния s_i' Î S' заданного НР, которые рассматриваются как одноэлементные подмножества.

б) Строятся подмножества состояний, в которые осуществляется переход из выписанных подмножеств, для каждого p_i' Î P'.

в) Если при построении подмножеств, в которые выполняется переход, не появилось новых подмножеств, то построение закончено.

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

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

Покажем, как применяется описанный способ на примере построения распознавателя А₁₁ для НР А₁₀, заданного таблицей переходов табл. 2.5.

Таблица 2.5. Таблица переходов НР А₁₀

	0	1
I	B	I,C
B	-	C
C	B	B

Этой таблице переходов соответствует диаграмма, изображенная на рис. 2.10

Рис. 2.10 Диаграмма переходов НР А₁₀

Последовательность построения таблицы переходов искомого распознавателя показана в таблице 2.6. В этой таблице имеется дополнительный столбец, в котором указан номер шага последовательности построения. На первом шаге в таблицу заносятся состояния I, B, C заданного недетерминированного распознавателя. Затем по таблице 2.5 определяются подмножества состояний, в которые выполняется переход для каждого входного символа. При этом обнаруживается, что переход из состояния I под действием единицы выполняется в подмножество IC. Появление этого подмножества говорит о необходимости выполнения второго шага последовательности. В соответствии с этим шагом добавим в таблицу новую строку для нового состояния IC и найдем множества состояний, в которые переходит НР из этого состояния. В результате получим новое состояние IBC. Добавив в таблицу новую строку для состояния IBC и выявив подмножества состояний, в которые осуществляется переход из IBC, покажем, что новые подмножества не образуются. Следовательно, построенную таблицу переходов можно рассматривать как таблицу переходов искомого детерминированного распознавателя, у которого состояния обозначены подмножествами состояний заданного НР.

Таблица 2.6. Таблица переходов распознавателя А₁₁

	0	1	шаг
I	B	IC	1
B	-	C
C	B	B
IC	B	IBC	2
IBC	B	IBC	3

Диаграмма переходов построенного распознавателя А₁₁ показана на рис. 2.11.

Рис. 2.11 Диаграмма переходов распознавателя А₁₁

Если задана автоматная грамматика и требуется построить распознаватель, допускающий язык, порождаемый этой грамматикой, то в большинстве случаев по виду правил грамматики можно определить будет распознаватель детерминированным или нет. Признаком того, что распознаватель будет недетерминированным, является наличие в схеме грамматики нескольких правил с одинаковой левой частью, правые части которых начинаются одним и тем же терминальным символом. Например, если в схему грамматики входят правила <A> ® b<C> и <A> ® b<D> , то соответствующий распознаватель получится недетерминированным.

---

Пред. страница   . След. страница   Раздел   Содержание