Обоснование алгоритма детерминизации конечных автоматов
В этом дополнении мы подробно докажем корректность приведенного в доказательстве теоремы 7.7 о детерминизации алгоритма построения по заданному конечному автомату эквивалентного ему детерминированного конечного автомата.
Сначала докажем корректность алгоритма удаления λ-переходов, после чего подобное доказательство проведем уже для самого алгоритма детерминизации.
1. Корректность алгоритма удаления λ-переходов
Пусть — исходный конечный автомат, а — конечный автомат без λ-переходов, построенный согласно алгоритму, описанному в доказательстве теоремы 7.7 о детерминизации. Мы должны доказать, что .
а. Докажем, что для любых цепочки и состояния из того, что в конечном автомате цепочка читается на некотором пути из в , т.е. имеет место , следует, что в конечном автомате эта цепочка читается на некотором пути из в такое состояние , что в имеет место , т.е. либо , либо в существует путь ненулевой длины по пустым дугам из в : (на рис. 7.32 и на аналогичных следующих рисунках мы соединяем тонкой штриховой линией кружки, изображающие одно и то же состояние, которое остается после удаления λ-переходов).
Возможны два случая для состояния : оно или остается после удаления λ-переходов, т.е. , либо удаляется в результате удаления λ-переходов, т.е. .
1°. Состояние остается после удаления λ-переходов, т.е. .
Проведем индукцию по длине пути в конечном автомате , на котором читается цепочка . Для пути нулевой длины доказываемое тривиально. Пусть для всех доказываемое свойство имеет место, и пусть цепочка читается в на некотором пути длины из в , то есть . Тогда существует такое состояние , что в имеет место
(7.9) причем и .
Если , то , и тогда цепочка читается в конечном автомате на некотором пути длины .
При остается только использовать индукционное предположение, и тогда найдется такое состояние , что в имеется и в имеется , но так как в имеется , то в выполняется (рис. 7.33). Таким образом, мы, исходя из условия, что в имеется , нашли такое состояние , что в имеет место , а при этом в выполняется , что и требовалось доказать.
Пусть теперь , т.е. состояние г удаляется при удалении λ-переходов. Это значит, что в состояние заходят только дуги с меткой . Но поскольку на некотором пути из в в конечном автомате читается цепочка , то найдется такое состояние , что в будет иметь место , и (в частности, может быть и тогда )- Согласно предположению индукции, отсюда следует, что в имеется , где в , а так как в имеет место , то в имеется (рис. 7.34), и мы снова, исходя из условия, что в имеется , нашли в такое состояние , что цепочка читается в на некотором пути из начального состояния в , при том что в исходном конечном автомате из этого состояния ведет путь по пустым дугам в состояние .
Итак, случай в (7.9) проанализирован полностью.
Пусть . Если при этом , то, согласно предположению индукции, существует такое состояние , что в конечном автомате выполняется , при том что в имеется .
При , ввиду того что дуга конечного автомата , метка которой содержит символ а, останется и в конечном автомате , получаем, что в имеется , то есть в имеется .
При , т.е. в случае, когда в конечном автомате заключаем, что в существует тройка состояний , такая, что и . По построению конечного автомата отсюда получаем, что в . Тогда в будет выполняться , то есть (рис. 7.35). Случай тем самым полностью проанализирован.
Если же , т.е. состояние удаляется при переходе к конечному автомату , то тогда существует такое состояние , что в цепочка читается на некотором пути длины из в , а из в ведет путь ненулевой длины по пустым дугам, т.е. в конечном автомате имеется (рис. 7.36). Тогда, согласно предположению индукции, в имеется , где в . Тогда опять в возникает тройка состояний , такая, что и (см. рис. 7.36). По построению конечного автомата в нем будет выполнено . Итак, в имеется , т.е. в конечном автомате цепочка читается на некотором пути из в .
2°. Состояние удаляется при удалении λ-переходов, то есть .
В этом случае для некоторого будет выполняться в конечном автомате , откуда, согласно результатам, доказанным для случая 1°, в конечном автомате для некоторого , такого, что в имеется . Следовательно, в , то есть , что и требовалось доказать.
Итак, мы полностью доказали, что любая цепочка , читаемая в исходном конечном автомате на некотором пути из начального состояния в какое-то состояние , читается также и в автомате на некотором пути из начального состояния в такое состояние , что в имеет место .
б. Докажем, что для любых состояния и цепочки из того, что в конечном автомате цепочка читается на некотором пути из начального состояния в какое-то состояние , т.е. имеет место , следует, что в исходном конечном автомате цепочка читается также на некотором пути из в в .
Проведем опять индукцию по длине пути в конечном автомате , на котором читается цепочка . Для пути нулевой длины доказываемое тривиально. Предполагая, что доказываемое верно для любой длины пути, не превосходящей , допустим, что в имеется . Тогда для некоторого в имеет место , причем , а так как в нет λ-переходов, то , то есть не может быть пустой цепочкой. Согласно предположению индукции, отсюда следует, что в имеется . Далее, из того, что в есть дуга из в , на которой читается символ , то есть в , следует, что либо эта дуга есть и в исходном конечном автомате , и тогда в , либо в существует такое состояние , что . Как в том, так и в другом случае имеем в конечном автомате , т.е. в цепочка читается на некотором пути из начального состояния в состояние .
в. Пусть цепочка , т.е. для некоторого заключительного состояния цепочка читается на некотором пути из начального состояния в состояние . Тогда из п. а следует, что в цепочка читается на некотором пути из в такое состояние , что в . Если , то ; если же , т.е. в существует путь ненулевой длины по пустым дугам из в , то, согласно определению множества , имеем . Итак, .
Обратно, если , т.е. в имеет место , где , то, согласно п. б, и в . Но так как в множество попадают либо заключительные вершины конечного автомата , либо те его вершины, из которых заключительная вершина достижима по пустым дугам, то найдется такое , что в имеем и , то есть в конечном автомате , откуда .
Итак, что и обосновывает корректность алгоритма удаления λ-переходов.
2. Корректность алгоритма детерминизации
Пусть теперь — исходный конечный автомат без λ-переходов, а — детерминированный конечный автомат, построенный согласно алгоритму, описанному в доказательстве теоремы о детерминизации, т.е.
и для любого и любого имеем . Мы должны доказать, что .
а. Докажем, что для любых цепочки и состояния из того, что в цепочка читается на некотором пути из начального состояния в какое-то состояние , то есть , следует, что эта цепочка читается и в на некотором пути из состояния в состояние-множество , которое содержит , т.е. в имеется , где .
Доказательство проводим индукцией по длине пути в конечном автомате , на котором читается цепочка (так как в автоматах уже нет пустых дуг, т.е. λ-переходов, то длина пути всегда совпадает с длиной цепочки, читаемой на этом пути; поэтому индукцию по длине пути в данном случае можно рассматривать как индукцию по длине цепочки).
Случай пути длины нуль тривиален. Полагая доказываемое справедливым для всех путей, длина которых не больше , допустим, что цепочка читается в на некотором пути длины из в , то есть . Тогда найдется такое , что (где и )
(7.10)
Тогда, согласно предположению индукции, в конечном автомате цепочка у читается на некотором пути в такое , что . Так как конечный автомат является детерминированным по построению, то из его состояния-множества ведет дуга в некоторое состояние-множество и метка этой дуги содержит символ , то есть в . Докажем, что . Состояние есть объединение всех множеств при . В частности, при множество состояний в силу (7.10) содержит состояние . Следовательно, это состояние принадлежит и множеству , и тогда в имеет место , то есть .
б. Докажем теперь, что для любой цепочки и любого состояния из в следует в .
Проведем индукцию по длине цепочки . При , т.е. для пустой цепочки , утверждение выполняется тривиально. Пусть оно верно при всех , и пусть в . Отсюда для некоторого , то есть , в выполняется , причем и . Тогда, согласно предположению индукции, в имеется для каждого . Поскольку , то любой элемент в есть элемент некоторого множества при , т.е. в есть дуга . Но, как мы только что доказали, для любого состояния имеет место , т.е. для любого имеем в конечном автомате , откуда , что и требовалось доказать.
в. Теперь, если , т.е. цепочка читается в на некотором пути из начального состояния в одно из заключительных, а именно для некоторого , то, согласно результатам, доказанным в п. а, в цепочка читается на некотором пути из начального состояния в заключительное состояние , содержащее вершину , то есть и .
Обратно, если , то есть в , то для любого состояния будем иметь в конечном автомате имеем . Но состояние-множество обязательно содержит некоторое заключительное состояние исходного конечного автомата (состояние из подмножества ). Тогда для любого такого состояния получим в , что и означает .
Итак, и тем самым вся процедура детерминизации конечных автоматов полностью обоснована.
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|