É o idioma

8

É o idioma L={0n1mn and m are co-prime} sem contexto?

Eu acho que não é livre de contexto, porque parece muito complicado para um PDA decidir se dois números são co-primos ou não.

Tentei usar o lema de bombeamento sem sucesso.

Qualquer ajuda seria apreciada com prazer.

Editar:

Aqui está uma das minhas tentativas fracassadas com o lema de bombeamento:

Deixei Nseja uma constante. Dê uma nobrep de tal modo que p>N! e depois pegue a palavra z=0p1p+N!L. Deixeiz=uvwxy ser uma decomposição de z satisfazendo as condições do lema de bombeamento.

E se vx contém apenas zeros então |vx|=k é um número inteiro entre 1 e N. Definirmcomo . Para a palavram=N!/ki=m+1uviwxiy=0p+N!1p+N!L

No entanto, não consegui encontrar um número inteiro para os outros casos de decomposição.i

Robert777
fonte
1
Bem-vindo à Ciência da Computação ! Deixe-me direcioná-lo para nossas perguntas de referência que podem cobrir seu problema. Por favor, trabalhe com as perguntas relacionadas listadas lá, tente resolver seu problema novamente e edite para incluir suas tentativas, juntamente com os problemas específicos que você encontrou. Eu acho que o teorema de Parikh pode funcionar para você.
Raphael
2
Parikh deve funcionar, mas também bombeamento padrão / Ogden, certo?
Ran G.
Na verdade, é uma pergunta do questionário. Como não aprendemos o teorema de Parikh, provavelmente existe uma maneira de mostrar que ele não é livre de contexto com o lema de bombeamento ou com as propriedades de fechamento.
precisa saber é o seguinte
@Raphael, neste caso, o teorema de Parikh realmente não acrescenta nada além do lema de bombeamento direto (ou seja, de 0n1m pode obter tudo 0n+ka1m+kb para alguns a, b não tanto zero como k1) Mas não vejo nenhuma maneira de forçargcd(n+ka,m+kb)1.
vonbrand
@vonbrand Podemos trabalhar em L¯L(01)em vez de; veja aqui .
Raphael

Respostas:

4

Ridículo que eu não vi isso antes ...

A prova de que o idioma (chame-o L) não é livre de contexto é por contradição. PresumirL é livre de contexto, pelo lema de bombeamento para CFGs há uma constante N de modo que cada string σL de tal modo que |σ|N pode ser escrito σ=uvxyz com vyϵ tal que para todos k0 a corda uvkxykzL. Tomam,n primos diferentes (tais que gcd(m,n)=1) e m,n>2N, e pegue σ=0m1n. A corda bombeada será0m+ka1n+kb para algumas constantes a, b, não ambos zero, e tal que a<m e b<n (temos a,bN<m/2,n/2 a propósito m, nforam selecionados). O caso de um deles zero foi coberto pelo OP, então considerea,b0. Agora:

m+ka0(modn)n+kb0(modm)

Isso tem uma solução única k módulo mn pelo teorema do resto chinês (temos a<n, e como n é primo, gcd(a,n)=1; similarmenteb e m) e, portanto, podemos escrever:

m+ka0(modmn)n+kb0(modmn)
ou seja, mngcd(m+ka,n+kb). Contradição.
vonbrand
fonte
Obrigado pela sua resposta. Gostei da maneira como você abordou isso. No entanto, eu não entendo como você usou o teorema do restante chinês, se isso só pode ser aplicado a um sistema de congruências lineares da forma:
xb1(modm1)xb2(modm2)
precisa saber é o seguinte
@ Robert777, basta escrever kam(modn)e assim por diante.
vonbrand
1
mas você obtém uma congruência da forma:
axb(modm)
e não é o mesmo. Por exemplo, segcd(a,m)|bentão a congruência não tem soluções.
precisa saber é o seguinte
1
@ Robert777, você está absolutamente certo. Alterado para selecionarm, nprime. Obrigado!
vonbrand
Ok, depois de usarmos o teorema do restante chinês, por que podemos escrever essas congruências:
m+ka0(modmn)n+kb0(modmn)
precisa saber é o seguinte