complexidade da meia língua

Para qualquer idioma sobre , defina Em palavras, é composto por todos os para o qual existe uma de igual comprimento tal 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$

Um exercício no livro de Sipser pede para mostrar que é regular sempre que é. Vi duas soluções distintas e ambas envolvem uma explosão exponencial de estados. $L_{1/2}$ $L$

Pergunta: alguém pode construir uma família de idiomas modo que o autômato canônico para seja significativamente (digamos exponencialmente) maior que o de ? Até agora, meus melhores esforços aumentam o tamanho do estado em ! $\{L_n\}$ $(L_n)_{1/2}$ $L$ $+1$

fl.formal-languages automata-theory Aryeh
fonte

você não menciona a questão semi-óbvia da minimização do DFA. ainda não viram as provas, mas talvez elas não levem em conta. e uma minimização do DFA pós-execução na construção da prova pode simplificar significativamente o DFA ...?

vzn

As construções nas provas são abstratas e não está claro como minimizá-las através das técnicas padrão.

Aryeh

Você pode publicar a melhor família de idiomas que encontrou?

Diego de Estrada

isso não é necessário para responder ao seu Q, mas pode ser útil esboçar as construções. outra opção é para atacar o problema empiricamente com REFs aleatórios

vzn

complexidade da meia língua

Respostas: