сложность половины языка

Для любого языка над определите На словах состоит из всех , для которых есть одинаковой длины таким образом, что .Σ * L +1 / +2 = { х ∈ Σ * : х у ∈ L , у ∈ Σ | х | } . L 1 / 2 х у й у ∈ $L$$\Sigma^*$

Упражнение в книге Сипсера просит показать, что является регулярным, когда есть. Я видел два разных решения, и оба связаны с экспоненциальным взрывом состояний.$L_{1/2}$$L$

Вопрос: может ли кто-нибудь построить семейство языков так, чтобы канонический автомат для был значительно (скажем, экспоненциально) больше, чем для ? Мои лучшие усилия пока только увеличивают размер штата на !( Л п ) 1 / 2 л + $\{L_n\}$$(L_n)_{1/2}$$L$$+1$

См. Статью Майка Домарацкого «Сложность пропорциональных удалений».

http://dl.acm.org/citation.cfm?id=782471

http://www.cs.umanitoba.ca/~mdomarat/pubs/sc_jalc.ps