complexité de la demi-langue

Pour toute langue sur , définissez En d'autres termes, constituée de tous pour lesquels il existe un de longueur égale de telle sorte que . $L$ $\Sigma^*$

L_{1 / 2} = {X \in Σ^{*} : X y \in L, y \in Σ^{| X |}} .

$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$

L_{1 / 2}

$L_{1/2}$

x

$x$

y

$y$

x y \in L

$xy\in L$

Un exercice du livre de Sipser demande de montrer que est régulier chaque fois que est. J'ai vu deux solutions distinctes, et toutes deux impliquent une explosion exponentielle des États. $L_{1/2}$ $L$

Question: quelqu'un peut-il construire une famille de langages telle sorte que l'automate canonique pour soit significativement (disons exponentiellement) plus grand que celui pour ? Jusqu'à présent, mes meilleurs efforts n'augmentent la taille de l'état que de ! $\{L_n\}$ $(L_n)_{1/2}$ $L$ $+1$

fl.formal-languages automata-theory Aryeh
la source

vous ne mentionnez pas le problème semi-évident de la minimisation DFA. je n'ai pas vu les preuves mais peut-être qu'ils ne le prennent pas en compte. et une minimisation DFA post-exécution sur la construction de preuve pourrait simplifier considérablement le DFA ...?

vzn

Les constructions dans les preuves sont abstraites et il n'est pas du tout clair comment les minimiser via les techniques standard.

Aryeh

Pouvez-vous publier la meilleure famille de langues que vous avez trouvée?

Diego de Estrada

ce n'est pas nécessaire pour répondre à votre Q, mais il pourrait être utile d'esquisser les constructions. une autre option consiste à attaquer le problème de manière empirique avec des FSM aléatoires

vzn

complexité de la demi-langue

Réponses: