Linguagens sem contexto não fechadas, tornando-as "sem extensão"

Para um idioma $L$ , definir:

N E (L) = {x \in L : x is not the proper prefix of any string in L}

$NE(L) = \{x \in L : x \text{ is not the proper prefix of any string in } L\}$

Estou tentando mostrar que as linguagens sem contexto não estão fechadas nesta operação. Estou lutando há muito tempo, tentando encontrar um contra-exemplo, ou seja, um idioma $L$ de tal modo que $L$ é livre de contexto, mas $NE(L)$ não é livre de contexto e não surgiu nada. Eu apreciaria idéias ou dicas sobre idiomas para analisar.

Edit: Para a grande maioria das linguagens sem contexto, parece que $NE(L) = L$ ou $NE(L) = \varnothing$ . Estou tendo problemas até para encontrar idiomas candidatos.

formal-languages context-free closure-properties cemular
fonte

Deixei

L = {a^{n}} \cup {a^{n} b^{n}}

$L = \{a^n\} \cup \{a^nb^n\}$ , então

N E (L) = {a^{n} b^{n}}

$NE(L) = \{a^nb^n\}$ . Mas

N E (L) \neq L \land N E (L) \neq \emptyset

$NE(L) \neq L \wedge NE(L) \neq \varnothing$ .

Anton Trunov

Respostas:

Ao invés do idioma $L\subseteq \Sigma^*$ considere o idioma $L' =L\$\$$ , concatene cada sequência por duas cópias de $\$$ Onde $\$$ é um novo símbolo que não está $\Sigma$ .

Deixei $x\in \Sigma^*$ . Corda $x\$$ não é um prefixo adequado de $L'$ iff $x\$\$ \notin L'$ iff $x\notin L$ .

Isso deve começar você a ir.

Hendrik Jan
fonte

Estou encarando isso há um tempo agora, e só não estou vendo. Primeiramente,

x $

$x\$$ nem está em

L^{'}

$L'$ , então certamente não pode estar em

N E (L^{'})

$NE(L')$ (que é um subconjunto de

L^{'}

$L'$ ) Aplicar o critério "não é um prefixo adequado de

L^{'}

$L'$ ", precisamos começar com um

x \in L^{'}

$x \in L'$ , caso contrário, não estamos obtendo informações sobre

N E (L^{'})

$NE(L')$ . Estou entendendo algo errado aqui?

cemulate

Você está certo. Para contornar isso, acho que basta considerar

L^{'} = L $ $ \cup Σ^{*} $

$L' = L\$\$ \cup \Sigma^*\$$ em vez de.

Hendrik Jan

Ah, esperto. Então, essencialmente, podemos usar essa construção para mostrar que se

C F L

$CFL$ foram fechados sob

N E

$NE$ , teria que ser fechado em complemento para derivar uma contradição. Como alternativa, basta escolher um idioma cujo complemento não seja CFL para obter um contra-exemplo. Obrigado, eu não sei quando eu teria pensado em algo assim ...

cemulate

@AntonTrunov Minha sugestão para o caso "genérico": as duas partes da linguagem podem ser distinguidas por suas caudas. Para que possamos isolar

C (L) $

$C(L)\$$ cruzando com regular

Σ^{*} $

$\Sigma^*\$$ .

Hendrik Jan

@AntonTrunov Desculpe, eu deveria ter sido mais preciso. Os idiomas sem contexto são fechados sob interseção com os idiomas regulares.

Hendrik Jan