Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Обоснование алгоритма детерминизации конечных автоматов

Обоснование алгоритма детерминизации конечных автоматов


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


Сначала докажем корректность алгоритма удаления λ-переходов, после чего подобное доказательство проведем уже для самого алгоритма детерминизации.


1. Корректность алгоритма удаления λ-переходов


Кружки, изображающие одно и то же состояние, которое остается после удаления ламбда-переходов

Пусть M=(V,Q,q_0,F,\delta) — исходный конечный автомат, а M'=(V,Q',q_0,F',\delta') — конечный автомат без λ-переходов, построенный согласно алгоритму, описанному в доказательстве теоремы 7.7 о детерминизации. Мы должны доказать, что L(M)=L(M').


а. Докажем, что для любых цепочки x\in V^{\ast} и состояния q\in Q из того, что в конечном автомате M цепочка x читается на некотором пути из q_0 в q, т.е. имеет место q_0\Rightarrow_{x}^{\ast}q, следует, что в конечном автомате M' эта цепочка читается на некотором пути из q_0 в такое состояние p\in Q', что в M имеет место p\Rightarrow_{\lambda}^{\ast}q, т.е. либо p=q, либо в M существует путь ненулевой длины по пустым дугам из p в q: p\Rightarrow_{\lambda}^{+}q (на рис. 7.32 и на аналогичных следующих рисунках мы соединяем тонкой штриховой линией кружки, изображающие одно и то же состояние, которое остается после удаления λ-переходов).


Возможны два случая для состояния q\in Q: оно или остается после удаления λ-переходов, т.е. q\in Q', либо удаляется в результате удаления λ-переходов, т.е. q\notin Q'.


1°. Состояние q остается после удаления λ-переходов, т.е. q\in Q'.


Проведем индукцию по длине пути в конечном автомате M, на котором читается цепочка x. Для пути нулевой длины доказываемое тривиально. Пусть для всех k\leqslant n-1 доказываемое свойство имеет место, и пусть цепочка x читается в M на некотором пути длины n из q_0 в q, то есть q_0\Rightarrow_{x}^{n}q. Тогда существует такое состояние r\in Q, что в M имеет место


q_0\Rightarrow_{y}^{n-1}r\to_{a}q,
(7.9)

причем x=ya и a\in V\cup\{\lambda\}.


Если a=\lambda, то x=y, и тогда цепочка x читается в конечном автомате M на некотором пути длины (n-1).


2. Кружки, изображающие одно и то же состояние, которое остается после удаления ламбда-переходов

При r\in Q' остается только использовать индукционное предположение, и тогда найдется такое состояние r'\in Q', что в M' имеется q_0\Rightarrow_{x}^{\ast}r' и в M имеется r'\Rightarrow_{\lambda}^{\ast}r, но так как в M имеется r\to_{\lambda}q, то в M выполняется r'\Rightarrow_{\lambda}^{\ast}q (рис. 7.33). Таким образом, мы, исходя из условия, что в M имеется q_0\Rightarrow_{x}^{n}q, нашли такое состояние r'\in Q', что в M' имеет место q_0\Rightarrow_{x}^{\ast}r', а при этом в M выполняется r'\Rightarrow_{\lambda}^{+}q, что и требовалось доказать.


Пусть теперь r\notin Q', т.е. состояние г удаляется при удалении λ-переходов. Это значит, что в состояние r заходят только дуги с меткой \lambda. Но поскольку на некотором пути из q_0 в r в конечном автомате M читается цепочка y, то найдется такое состояние p\in Q', что в M будет иметь место q_0\Rightarrow_{y}^{m}p \Rightarrow_{\lambda}^{\ast}r, и m<n-1 (в частности, может быть m=0 и тогда p=q_0)- Согласно предположению индукции, отсюда следует, что в M' имеется q_0\Rightarrow_{y=x}^{\ast}p', где p'\Rightarrow_{\lambda}^{\ast}p в M, а так как в M имеет место p\Rightarrow_{\lambda}^{\ast}r\to_{\lambda}q, то в M имеется p'\Rightarrow_{\lambda}^{+}q (рис. 7.34), и мы снова, исходя из условия, что в M имеется q_0\Rightarrow_{x}^{n}q, нашли в Q' такое состояние p', что цепочка x читается в M' на некотором пути из начального состояния в p', при том что в исходном конечном автомате M из этого состояния p' ведет путь по пустым дугам в состояние q.


Итак, случай a=\lambda в (7.9) проанализирован полностью.


3. Кружки, изображающие одно и то же состояние, которое остается после удаления ламбда-переходов

Пусть a\ne\lambda. Если при этом r\in Q', то, согласно предположению индукции, существует такое состояние r'\in Q', что в конечном автомате M' выполняется q_0\Rightarrow_{y}^{\ast}r', при том что в M имеется r'\Rightarrow_{\lambda}^{\ast}r.


При r'=r, ввиду того что дуга (r,q) конечного автомата M, метка которой содержит символ а, останется и в конечном автомате M', получаем, что в M' имеется q_0\Rightarrow_{y}^{\ast}r\to_{a}q, то есть в M' имеется q_0\Rightarrow_{x}^{\ast}q.


4. Кружки, изображающие одно и то же состояние, которое остается после удаления ламбда-переходов

При r'\ne r, т.е. в случае, когда r'\Rightarrow_{\ast}^{+}r в конечном автомате M заключаем, что в M существует тройка состояний r',r,q, такая, что r'\Rightarrow_{\lambda}^{+} и r\to_{a}q. По построению конечного автомата M' отсюда получаем, что r'\to_{a}q в M'. Тогда в M' будет выполняться q_0\Rightarrow_{y}^{\ast} r'\to_{a}q, то есть q_0\Rightarrow_{x}^{\ast}q (рис. 7.35). Случай r\in Q' тем самым полностью проанализирован.


Если же r\notin Q', т.е. состояние r удаляется при переходе к конечному автомату M', то тогда существует такое состояние p\in Q', что в M цепочка y читается на некотором пути длины m<n-1 из q_0 в p, а из p в r ведет путь ненулевой длины по пустым дугам, т.е. в конечном автомате M имеется q_0\Rightarrow_{p}^{m} \Rightarrow_{\lambda}^{+}r (рис. 7.36). Тогда, согласно предположению индукции, в M' имеется q_0\Rightarrow_{y}^{\ast}p', где p'\Rightarrow_{\lambda}^{\ast}p в M. Тогда опять в M возникает тройка состояний p',r,q, такая, что p'\Rightarrow_{\lambda}^{+}r и r\to_{a}q (см. рис. 7.36). По построению конечного автомата M' в нем будет выполнено p'\to_{a}q. Итак, в M' имеется q_0\Rightarrow_{y}^{\ast}p'\to_{a}q, т.е. в конечном автомате M' цепочка x читается на некотором пути из q_0 в q\colon~ q_0\Rightarrow_{x}^{\ast}q.


5. Кружки, изображающие одно и то же состояние, которое остается после удаления ламбда-переходов

2°. Состояние q удаляется при удалении λ-переходов, то есть q\notin Q'.


В этом случае для некоторого r\in Q' будет выполняться q_0\Rightarrow_{x}^{\ast} r\Rightarrow_{\lambda}^{+}q в конечном автомате M, откуда, согласно результатам, доказанным для случая 1°, q_0\Rightarrow_{x}^{\ast}r' в конечном автомате M' для некоторого r'\in Q', такого, что в M имеется r'\Rightarrow_{\lambda}^{\ast}r. Следовательно, r'\Rightarrow_{\lambda}^{\ast}r\Rightarrow_{\lambda}^{+}q в M, то есть r'\Rightarrow_{\lambda}^{\ast}q, что и требовалось доказать.


Итак, мы полностью доказали, что любая цепочка x, читаемая в исходном конечном автомате M на некотором пути из начального состояния q_0 в какое-то состояние q, читается также и в автомате M' на некотором пути из начального состояния q_0 в такое состояние p, что в M имеет место p\Rightarrow_{\lambda}^{\ast}q.




б. Докажем, что для любых состояния q\in Q' и цепочки x\in V^{\ast} из того, что в конечном автомате M' цепочка x читается на некотором пути из начального состояния q_0 в какое-то состояние q, т.е. имеет место q_0\Rightarrow_{x}^{\ast}q, следует, что в исходном конечном автомате M цепочка x читается также на некотором пути из q_0 в q\colon~ q_0\Rightarrow_{x}^{\ast}q в M.


Проведем опять индукцию по длине пути в конечном автомате M', на котором читается цепочка x. Для пути нулевой длины доказываемое тривиально. Предполагая, что доказываемое верно для любой длины пути, не превосходящей n-1, допустим, что в M' имеется q_0\Rightarrow_{x}^{n}q. Тогда для некоторого r\in Q' в M' имеет место q_0\Rightarrow_{y}^{n-1}r\to_{a}q, причем ya=x, а так как в M' нет λ-переходов, то a\in V, то есть a не может быть пустой цепочкой. Согласно предположению индукции, отсюда следует, что в M имеется q_0\Rightarrow_{y}^{\ast}r. Далее, из того, что в M' есть дуга из r в q, на которой читается символ a, то есть r\to_{a}q в M', следует, что либо эта дуга есть и в исходном конечном автомате M, и тогда r\to_{a}q в M, либо в M существует такое состояние p, что r\Rightarrow_{\lambda}^{+}p\to_{a}q. Как в том, так и в другом случае имеем q_0\Rightarrow_{y}^{\ast}r\Rightarrow_{a}^{+}q в конечном автомате M, т.е. в M цепочка x читается на некотором пути из начального состояния в состояние q\colon~ q_0\Rightarrow_{x}^{\ast}q.




в. Пусть цепочка x\in L(M), т.е. для некоторого заключительного состояния f\in F цепочка x читается на некотором пути из начального состояния в состояние f\colon\, q_0\Rightarrow_{x}^{\ast}f. Тогда из п. а следует, что в M' цепочка x читается на некотором пути из q_0 в такое состояние f', что f'\Rightarrow_{\lambda}^{\ast}f в M. Если f'=f, то f'\in F'; если же f'\ne f, т.е. в M существует путь ненулевой длины по пустым дугам из f' в f, то, согласно определению множества F', имеем f'\in F'. Итак, x\in L(M').


Обратно, если x\in L(M'), т.е. в M' имеет место q_0\Rightarrow_{x}^{\ast}f', где f'\in F', то, согласно п. б, q_0\Rightarrow_{x}^{\ast}f' и в M. Но так как в множество F' попадают либо заключительные вершины конечного автомата M, либо те его вершины, из которых заключительная вершина достижима по пустым дугам, то найдется такое f\in F, что в M имеем f'\Rightarrow_{\lambda}^{+}f и q_0\Rightarrow_{x}^{\ast}f'\Rightarrow_{\lambda}^{+}f, то есть q_0\Rightarrow_{x}^{\ast}f в конечном автомате M, откуда x\in L(M).


Итак, L(M)=L(M') что и обосновывает корректность алгоритма удаления λ-переходов.




2. Корректность алгоритма детерминизации


Пусть теперь M=(V,Q,q_0,F,\delta) — исходный конечный автомат без λ-переходов, а M'=(V,Q',q'_0,F',\delta') — детерминированный конечный автомат, построенный согласно алгоритму, описанному в доказательстве теоремы о детерминизации, т.е.


Q'=2^Q,\qquad q'_0=\{q_0\},\qquad F'=\{S\colon\, S\cap F\ne\varnothing\},

и для любого S\subseteq Q и любого a\in V имеем \delta'(S,a)=\bigcup\limits_{q\in S}\delta(q,a). Мы должны доказать, что L(M)=L(M').


а. Докажем, что для любых цепочки x\in V^{\ast} и состояния q\in Q из того, что в M цепочка x читается на некотором пути из начального состояния q_0 в какое-то состояние q, то есть q_0\Rightarrow_{x}^{\ast}q, следует, что эта цепочка читается и в M' на некотором пути из состояния \{q_0\} в состояние-множество S, которое содержит q, т.е. в M имеется \{q_0\}\Rightarrow_{x}^{\ast}S, где q\in S.


Доказательство проводим индукцией по длине пути в конечном автомате M, на котором читается цепочка x (так как в автоматах уже нет пустых дуг, т.е. λ-переходов, то длина пути всегда совпадает с длиной цепочки, читаемой на этом пути; поэтому индукцию по длине пути в данном случае можно рассматривать как индукцию по длине цепочки).


Случай пути длины нуль тривиален. Полагая доказываемое справедливым для всех путей, длина которых не больше n-1, допустим, что цепочка x читается в M на некотором пути длины n из q_0 в q, то есть q_0\Rightarrow_{x}^{n}q. Тогда найдется такое r\in Q, что (где x=ya и a\in V)


q_0\Rightarrow_{y}^{n-1}r\to_{a}q,
(7.10)

Тогда, согласно предположению индукции, в конечном автомате M' цепочка у читается на некотором пути \{q_0\} в такое R, что r\in R\colon\,\{q_0\}\Rightarrow_{y}^{\ast}R. Так как конечный автомат M' является детерминированным по построению, то из его состояния-множества R ведет дуга в некоторое состояние-множество S и метка этой дуги содержит символ a, то есть R\to_{a}S в M'. Докажем, что S\ni q. Состояние S=\delta'(R,a) есть объединение всех множеств \delta(p,a) при p\in R. В частности, при p=r множество состояний \delta(r,a) в силу (7.10) содержит состояние q. Следовательно, это состояние принадлежит и множеству S, и тогда в M' имеет место \{q_0\}\Rightarrow_{y}^{\ast}R\to_{a}S, то есть \{q_0\}\Rightarrow_{x}^{\ast}S\ni q.


б. Докажем теперь, что для любой цепочки x\in V^{\ast} и любого состояния S\in Q' из \{q_0\}\Rightarrow_{x}^{\ast}S в M' следует (\forall q\in S)(q_0\Rightarrow_{x}^{\ast}r) в M.


Проведем индукцию по длине цепочки x. При |x|=0, т.е. для пустой цепочки x, утверждение выполняется тривиально. Пусть оно верно при всех k\leqslant n-1, и пусть \{q_0\}\Rightarrow_{x}^{n}S в M'. Отсюда для некоторого R\in Q', то есть R\subseteq Q, в M' выполняется \{q_0\}\Rightarrow_{y}^{n-1}R\to_{a}S, причем x=ya и a\in V. Тогда, согласно предположению индукции, в M имеется q_0\Rightarrow_{y}^{\ast}r для каждого r\in R. Поскольку S=\delta'(R,a), то любой элемент q в S есть элемент некоторого множества \delta(r,a) при r\in R, т.е. в M есть дуга r\to_{a}q. Но, как мы только что доказали, для любого состояния r\in R имеет место q_0\Rightarrow_{y}^{\ast}r, т.е. для любого q\in S имеем q_0\Rightarrow_{y}^{\ast}r\to_{a}q в конечном автомате M, откуда (\forall q\in S)(M\colon\,q_0\Rightarrow_{x}^{\ast}q), что и требовалось доказать.


в. Теперь, если x\in L(M), т.е. цепочка x читается в M на некотором пути из начального состояния в одно из заключительных, а именно q_0\Rightarrow_{x}^{\ast}f для некоторого f\in F, то, согласно результатам, доказанным в п. а, в M' цепочка x читается на некотором пути из начального состояния в заключительное состояние S_f, содержащее вершину f\colon\,\{q_0\}\Rightarrow_{x}^{\ast}S_f\ni f, то есть S_f\in F' и x\in L(M').


Обратно, если x\in L(M'), то есть \{q_0\}\Rightarrow_{x}^{\ast}S_f\in F' в M', то для любого состояния q\in S_f будем иметь в конечном автомате M имеем q_0\Rightarrow_{x}^{\ast}q. Но состояние-множество S_f обязательно содержит некоторое заключительное состояние исходного конечного автомата M (состояние из подмножества F). Тогда для любого такого состояния f\in S_f\cap F получим q_0\Rightarrow_{x}^{\ast}f в M, что и означает x\in L(M).


Итак, L(M)=L(M') и тем самым вся процедура детерминизации конечных автоматов полностью обоснована.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved