Оцените количество состояний в DFA (пересечение)

У меня возникли проблемы с пониманием того, как оценить количество состояний на пересечении двух DFA (M1 и M2, которые имеют n и k состояний). Я не хочу строить настоящий DFA, а хочу понять, сколько состояний даст пересечение. Например, объединение M1 и M2 даст |n| х |к| состояния (если я правильно понял). Есть ли кто-нибудь, кто мог бы помочь мне понять эту проблему? У меня есть некоторые трудности с пониманием DFA...


intersection dfa finite-automata
person user2795095    schedule 30.01.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Имея два DFA D1 и D2 с n1 и n2 состояниями соответственно, можно построить новый DFA D3 с n1n2 состояниями в нем, язык которого является пересечением языков D1 sub> и D2 с помощью конструкции продукта: пусть состояния D соответствуют парам состояний, одно из D1 и одно из D2, и где состояния принятия соответствуют парам состояний принятия из D1 и D2.

Тем не менее, это не обязательно будет DFA с минимальным состоянием для пересечения. Это будет просто немного DFA для пересечения.

person templatetypedef    schedule 31.01.2014