E se

Estou interessado em provar que $\sqrt{L}=\{w:ww\in L\}$ é regular se $L$ é regular, mas parece que não estou chegando a lugar algum. Se possível, eu estava esperando uma dica para me levar na direção certa. Obrigado pela ajuda.

Minha idéia para demonstrar a regularidade da linguagem raiz quadrada foi tentar considerar duas máquinas rodando em conjunto. Um deles aceita o idioma original $L$ e o outro executa a mesma máquina ao contrário (espero que seja um NFA). Eu queria aceitar as palavras que se encontravam no meio (isto é, ${(q,q):q∈Q}$ Onde $Q$ são os estados do DFA que aceitam $L$ ) No entanto, não acho que isso funcione.

formal-languages regular-languages finite-automata closure-properties user99163
fonte

A seguir, há uma resposta em math.sx: Se

L

$L$ é regular, prove que

\sqrt{L} = {w : w w \in L}

$\sqrt{L}=\left\{ w : ww\in L\right\}$ é regular

Pål GD

As duas máquinas devem correr para a frente. É só que o segundo deve começar onde o primeiro terminará. Portanto, o segundo deve adivinhar seu estado inicial e lembrar-se desse palpite.

babou

@ PålGD Obrigado pela sua resposta. Essa é uma solução interessante, mas não consigo fazer com que a indução funcione na etapa indutiva. O que recebo é o seguinte:

\hat{δ^{'}} (q_{0}^{'}, w a) = δ^{'} (\hat{δ^{'}} (q_{0}^{'}, w), a) = δ^{'} (f, a) = g

$\hat{\delta'}(q_{0}',wa)=\delta'(\hat{\delta'}(q_{0}',w),a)=\delta'(f,a)=g$ Onde

f (q) = \hat{δ} (q, w)

$f(q)=\hat{\delta}(q,w)$ pela hipótese indutiva. assim

g (q) = f (δ (q, b)) = \hat{δ} (δ (q, b), w) = \hat{δ} (q, b w)

$g(q)=f(\delta(q,b))=\hat{\delta}(\delta(q,b),w)=\hat{\delta}(q,bw)$ Se você pudesse me dizer onde errei, ficaria grato.

user99163

@babou Obrigado pela sua resposta. Você está sugerindo um NFA no qual possa iniciar em qualquer ponto do DFA original que aceite

L

$L$ ?

user99163

Sim. Isso é feito com um método não determinístico

ϵ

$\epsilon$ -transição no começo. Os estados são triplos do estado original da máquina, um para a primeira simulação, um para a segunda simulação e outro para lembrar onde a segunda simulação foi iniciada, para garantir que a primeira termine lá.

babou

Respostas:

Aqui está como implementar sua solução. Deixei $A = \langle Q, q_0, F, \delta \rangle$ ser um DFA para $L$ . Vamos construir uma NFA $A' = \langle Q', q'_0, F', \delta' \rangle$ do seguinte modo:

$Q' = \{q'_0\} \cup Q^3$ . O Estado $(q_1,q_2,q_3)$ significa que adivinhamos que quando $A$ termina de ler a primeira cópia do $w$ , estará no estado $q_1$ ; a primeira cópia de $A$ , começou às $q_0$ , está no estado $q_2$ ; e a segunda cópia de $A$ , começou às $q_1$ , está no estado $q_3$ .
$F' = \{(q_1,q_1,q_2) : q_1 \in Q, q_2 \in F\}$ . Assim, aceitamos se a primeira cópia do $A$ está no estado adivinhado e a segunda cópia do $A$ está em um estado de aceitação.
$\delta'(q'_0,\epsilon) = \{(q,q_0,q) : q \in Q\}$ . Isso inicializa a simulação das duas cópias do $A$ .
$\delta'((q_1,q_2,q_3),a) = \{(q_1,\delta(q_2,a),\delta(q_3,a))\}$ . Isso simula as duas cópias do $A$ , mantendo o estado adivinhado.

Deixamos ao leitor a prova formal de que $L(A') = \sqrt{L(A)}$ .

Aqui está outra solução, que cria um DFA. Agora corremos $|Q|$ cópias de $A$ em paralelo, começando em cada estado de $A$ :

$Q' = Q^Q$ .
$q'_0 = q \mapsto q$ , a função de identidade.
$\delta'(f,a) = q \mapsto \delta(q,a)$ .
$F' = \{ f \in Q' : f(f(q_0)) \in F \}$ .

Qual é o significado da condição $f(f(q_0)) \in F$ ? Depois de ler uma palavra $w$ , o autômato $A'$ está em um estado $f$ dado por $f(q) = \delta(q,w)$ . portanto $f(f(q_0)) = \delta(\delta(q_0,w),w) = \delta(q_0,w^2)$ .

Yuval Filmus
fonte

Pode haver muitos tipos dessas funções, como SQRT (L), MEIA (L), etc. Existe alguma maneira geral de combinar todas elas? Eu estava pensando nas linhas do Teorema de Myhill Nerode. Isso é o que também é chamado de metade. sqrt é

\exists y

$\exists y$ st

| y | = | x |^{2}

$|y|=|x|^2$ e

x y \in L

$xy\in L$

Usuário não encontrado