Como as soluções de uma equação diofantina podem ser expressas como uma linguagem?

Foi-me dada a pergunta

Onde o idioma a seguir se encaixa na hierarquia de Chomsky?

Soluções não negativas $(x,y)$ para a equação diofantina $3x-y=1$.

Eu entendo idiomas como $L = \{ 0^n1^n \mid n \ge 1\}$, mas esse idioma me confunde. Como são as palavras no idioma? Como eu poderia representá-lo usando uma gramática ou expressão regular?

A primeira coisa que você deseja fazer é olhar para a própria frase e ignorar todas as referências a idiomas por um momento.

Então, quais são as soluções não negativas para a equação diofantina $3x-y=1$? Se consertarmos alguns$x$, então $y = 3x-1$. Isso significa que o conjunto de soluções é$\{ (x, 3x-1)\ |\ x > 0 \}$ (Observe que $x=0$ produz um negativo $y$e positivo $x$ produz um positivo $y$)

Agora, podemos associar uma string a qualquer par de números não negativos $(x, y)$: por exemplo, $(100, 299)$pode ser associado à sequência (100, 299). Se aplicarmos isso a todos os pares do conjunto, o conjunto de seqüências resultante será o idioma desse conjunto. Observe que a pergunta realmente não deixa claro como associar uma string a uma solução, mas tenho certeza de que elas significam o que foi dito acima.

Agora tudo o que você precisa fazer é descobrir em que nível da hierarquia de Chomsky esse idioma se enquadra. Como tenho uma leve suspeita de que essa é uma pergunta de lição de casa, não vou derramar o feijão imediatamente. Se você puder confirmar que essa não é uma pergunta de lição de casa e ainda precisar de ajuda, editarei a resposta em

A declaração do problema é realmente incompleta, mas quando você vê isso, pode assumir com segurança que “ representando números inteiros em notação decimal ” ou “ representando números inteiros em notação binária ” foi feito.

Então, aqui, se assumirmos notação binária, o alfabeto é contém 5 caracteres: 0, 1, (, )e ,. Se assumirmos notação decimal, o alfabeto seria adicionalmente, conter os dígitos 2através 9.

O idioma em questão é um subconjunto do idioma correspondente à expressão regular $\mathtt{(}(0|1)^*\mathtt{,}(0|1)^*\mathtt{)}$(indo com notação binária). Se assumirmos o caso mais simples da equação$2x-y=0$, então o idioma seria todos os pares de números $(x,y)$ de tal modo que $y = 2x$. Em binário, isso significa$y$ é $x$com um adicional 0no final. Em outras palavras, o idioma consistiria em palavras da forma($x$,$x$0). Onde isso se encaixa na hierarquia de Chomsky?

Aqui, temos um exemplo mais complicado: você precisa reconhecer se $y = 3x-1$. Como expansões binárias (ou decimais) de$x$ e $y$ comparar quando $y=3x-11$?

A questão não está completa, pois um idioma é um conjunto de palavras, não pares. Se você o codificar como$x\$y$ Onde $x,y$ são binários, é sensível ao contexto, mas não livre de contexto (consulte a resposta de Gilles), se você o codificar como $x\$y^R$ é livre de contexto, mas não é regular (exercício), se você intercalar adequadamente pedaços de $x$ e $y$, é regular! Veja aqui .