Рассмотрим язык , где - новый символ. Сложность NFA равна . Мы покажем, что сложность покрытия DFA равна . # M n n 2 nMn=ϵ+(Ln#)∗Ln#Mnn2n
Пусть - DFA, принимающий некоторый язык с функцией перехода . Назовите состояние жизнеспособным, если существует какое-то слово такое, что является принимающим состоянием. Для любых двух безотказных состояний пустьНетрудно проверить, что каждое слово может быть записано как где для некоторого жизнеспособного .L ( A ) ⊆ M n q A s w q A ( s , w ) s , t A s , t = { w ∈ ( 1 + ⋯ + n ) ∗ : q A ( s , w ) = t } . w ∈ L ( A ) w = w 1 #AL(A)⊆MnqAswqA(s,w)s,t
As,t= {w∈(1+⋯+n)∗:qA( с , ш ) =t}.
w∈L(A)w i ∈ A s i , t i s i , t iw=w1#⋯#wlwi∈Asi,tisi,ti
Предположим, что , где каждый является DFA. Пусть - решетка, порожденная всеми языками . Мы можем рассматривать как язык над , пробелом между любыми двумя символами, соответствующими . Согласно этой точке зрения, соответствует .A i P A i s , t L ( A i ) L P ( A i ) P ∗ # M n P ∗Mn=⋃Ni=1L(Ai)AiPAis,tL(Ai)LP(Ai)P∗#MnP∗
Назовем универсальным, если для некоторого это тот случай, когда для всех найдется такой, что . Покажем, что некоторая универсальна. В противном случае каждый содержит не более слов длины . В общей сложности должно содержать все слова длины , следовательно, , что нарушается при достаточно большом .x ∈ P ∗ y ∈ P z ∈ P ∗ x y z ∈ L P ( A i ) L P ( A i ) L P ( A i ) ( | P | - 1 ) l l L P ( A i ) | P | л л | пLP(Ai) x∈P∗y∈Pz∈P∗xyz∈LP(Ai)LP(Ai)LP(Ai)(|P|−1)llLP(Ai)|P|ll l|P|l≤N(|P|−1)ll
Предположим, что универсален, и для краткости напишите . Пусть будет соответствующим префиксом, и пусть будет некоторым словом, соответствующим ему. Таким образом, для каждого существует некоторый такой, что .A = A i x ′ ∈ P ∗ x ∈ M n y ∈ L n z y ∈ M n x # y # z y ∈ L ( A i )LP(Ai)A=Aix′∈P∗x∈Mny∈Lnzy∈Mnx#y#zy∈L(Ai)
Для подмножества , пусть состоит из букв в написанных по порядку. Мы утверждаем , что слова неэквивалентны для Myhill-Nerode отношения . Действительно, предположим, что и найдем некоторый (без ограничения общности). Тогда то время как . Следовательно, должно иметь не менее состояний.y S S x # y S A S ≠ T a ∈ S ∖ T x # y T y { 1 , … , n } - a # z y T y { 1 , … , n } - a ∈ L ( A ) x # yS⊆{1,…,n}ySSx#ySAS≠Ta∈S∖Tx#yTy{1,…,n}−a#zyTy{1,…,n}−a∈L(A)x#ySy{1,…,n}−a#zyTy{1,…,n}−a∉MnA2n