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

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

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

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

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


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

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


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


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


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


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

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


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


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


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


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


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

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


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


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

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


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


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


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

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


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


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

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


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


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

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


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


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




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


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




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


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


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




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


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


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

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


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


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


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


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

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


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


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


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


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


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


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


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

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