Пусть M1 и M2 - минимальные детерминированные конечные автоматы, приемлемыми языками которых являются L1 и L2 соответственно.
Сначала построим детерминированный конечный автомат M3, принятым языком которого является пересечение L1 и L2, используя декартовуПродукт Машинная конструкция - алгоритм, который производит желаемую машину.
Затем создайте детерминированный конечный автомат M4, который принимает тот же язык, что и M3, но который минимален;то есть минимизируйте M3 и назовите результат M4.Существует алгоритм, который дает этот результат.
Затем создайте детерминированный конечный автомат M5, который принимает только слова длины, строго превышающей k, где k - число состояний в M4.Существует такая машина с k + 1 состояниями для любого алфавита;его построение несложно.
Далее создадим детерминированный конечный автомат M6, принятый язык которого является пересечением языков, принятых M4 и M5.Здесь снова используем конструкцию машины декартовых произведений.
Затем создайте детерминированный конечный автомат M7 путем минимизации M6.
В этот момент либо M6 является детерминированным конечным автоматом с одним состоянием, которое не принимает никакихструны вообще или нет.В первом случае пересечение L1 и L2 конечно;в последнем случае это пересечение бесконечно.Почему?
- M1 принимает L1
- M2 принимает L2
- M3 принимает L1-пересечение L2
- M4 - DFA принимает L1-пересечение L2 и имееткак можно меньше состояний
- M5 принимает только слова, которые заставили бы M4 дважды войти в одно из его состояний
- M6 принимает только слова в L1, пересекают L2, что также заставляет M4 войти в одно из его состоянийдважды.Обратите внимание, что если M6 принимает что-либо, это означает, что в L1 есть слова, пересекающие L2, которые должен принимать цикл DFA для этого языка;поскольку за такой петлей можно следовать любое количество раз, это означает, что в L1 должно быть бесконечно много слов, пересекающих L2.Это тесно связано с леммой прокачки для обычных языков.
- M7 принимает то, что делает M6, но минимально.Обратите внимание, что минимизация не является необходимой, но она делает тривиальной проверку, принимает ли M6 что-либо или нет.Минимальный DFA, который не принимает ни одной строки, имеет одно мертвое состояние.Это легко проверить, и существуют стандартные алгоритмы минимизации.
Еще один похожий способ показать то же самое - сказать, что вы можете построить DFA для пересечения, а затем проверить все строки длины.из | Q |до | 2 кв.Ни один конечный язык не будет иметь строк такой длины, принятых DFA для этого языка, но каждый бесконечный язык будет иметь хотя бы одну такую строку.Это связано с тем, что любой DFA, принимающий бесконечный язык, должен выполнить цикл, и длина этого цикла не должна превышать количество состояний.