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

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

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

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


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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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


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

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

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

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

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

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

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


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

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


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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: