A transformação a seguir preserva a transparência do contexto?

Encontrei esse problema envolvendo a manipulação de uma linguagem livre de contexto. Seja uma linguagem livre de contexto. Definir para cada . É sempre livre de contexto? Meu palpite é que preservará a transparência do contexto. Alguém pode fornecer uma prova elementar disso? $L$ $L^{\#} = \{ x : x^i \in L$ $i=0,1,2,...\}$ $L^{\#}$

formal-languages context-free guest100008
fonte

Quando você publica uma pergunta em dois sites, as pessoas agradecem se você deixar um comentário sobre a postagem cruzada, com um link para a pergunta no outro site.

Tara B

Comentário: para idiomas regulares, isso está correto. Vamos

, de modo que

tem um DFA com

estados, em seguida, para cada palavra

, se

estão todos em

, em seguida,

, para que possamos construir um DFA que reconheça

. O uso da finitude do DFA aqui sugere que a reivindicação pode não ser verdadeira para as lâmpadas fluorescentes compactas.

L \in R E G

$L\in REG$

L

$L$

n

$n$

x

$x$

x, x^{2}, . . ., x^{n + 1}

$x,x^2,...,x^{n+1}$

L

$L$

x \in L^{#}

$x\in L^\#$

L^{#}

$L^\#$

Shaull

student.cs.uwaterloo.ca/~cs462 Conjunto de problemas 7. Eu queria adicionar a tag lição de casa, mas que não funcionou (?)

Hendrik Jan

@HendrikJan Parece que eles não têm a tag lição de casa aqui

Виталий Олегович

@VitalijZadneprovskij Então parece! A solução está prevista para 5 de março de 2013. Portanto, responderei na próxima quarta-feira, quando ainda for necessário. Grande problema embora.

Hendrik Jan

Respostas:

Contra-exemplo:

$L_1 = \{a^n b^n c^m \mid m,n \ge 1 \}$

$L_2 = \{a^m b^n c^n \mid m,n \ge 1 \}$

é livre de contexto. $L = (L_1 \cdot L_2^*) \cup \epsilon$

Qualquer palavra não vazia tem um prefixo . Ele deve ser , porque, devido a , qualquer par de e um diretamente sucessivo em (após ) deve compartilhar o mesmo expoente. Portanto: $x \in L^\#$ $p = a^n b^n c^m \in L_1$ $n = m$ $L_2$ $b^+$ $c^+$ $x$ $p$

, que não é livre de contexto. $L^\# = (\{a^n b^n c^n \mid n \ge 1 \} \cdot L_2^*) \cup \epsilon$

Simon S
fonte

Não sei se entendi o que você quer dizer. Uma string como

está em

porque

, para que você possa produzir tudo potências de

com

x = a^{n} b^{n} c^{n} a^{k} b^{k} c^{k}

$x = a^n b^n c^n a^k b^k c^k$

L^{#}

$L^\#$

a^{n} b^{n} c^{n} \in L_{1}, L_{2}

$a^n b^n c^n \in L_1,L_2$

a^{k} b^{k} c^{k} \in L_{2}

$a^k b^k c^k \in L_2$

x

$x$

e assim por diante.

x^{2} \in L_{1} L_{2} L_{2} L_{2} \subset L

$x^2 \in L_1 L_2 L_2 L_2 \subset L$

Simon S

No entanto, percebi que coloquei

errado de alguma forma.

L^{#}

$L^\#$

Simon S

Na verdade, eu estava perdendo algumas seqüências de caracteres, mas meus argumentos não eram claros, eu concordo, e provavelmente errado, como está escrito. Agora parece bom para mim. Obrigado. Eu excluo esse comentário agora.

quer