Linguagem unária: diferenças entre revisões
m Página marcada como sem fontes, usando FastButtons. |
Erro ortográfico |
||
| Linha 48: | Linha 48: | ||
__NOTOC__ |
__NOTOC__ |
||
Em [[teoria da complexidade computacional]], uma '''linguagem unária''' ou '''linguagem de registro''' é uma [[linguagem formal]] (um conjunto de [[string (informática)|strings]]), onde todas as strings têm a forma de 1<sup>''k''</sup>, onde "1" pode ser qualquer símbolo arbitrário. Por exemplo, a linguagem {1, 111, 1111} é unária, como é a linguagem {1<sup>''k''</sup> | ''k'' é [[número primo|primo]]}. A [[classe de complexidade]] de todas essas |
Em [[teoria da complexidade computacional]], uma '''linguagem unária''' ou '''linguagem de registro''' é uma [[linguagem formal]] (um conjunto de [[string (informática)|strings]]), onde todas as strings têm a forma de 1<sup>''k''</sup>, onde "1" pode ser qualquer símbolo arbitrário. Por exemplo, a linguagem {1, 111, 1111} é unária, como é a linguagem {1<sup>''k''</sup> | ''k'' é [[número primo|primo]]}. A [[classe de complexidade]] de todas essas linguagens pode ser chamada de '''TALLY'''. |
||
O nome "unário" vem do fato de que uma língua unário é a codificação de um conjunto de [[números naturais]] no [[sistema de numeração unário]]. Como o universo das strings sobre qualquer alfabeto finito é um [[conjunto contável]], todas as linguagens podem ser mapeadas para um único conjunto A de números naturais, assim, cada linguagem tem uma ''versão unária'' {1<sup>''k''</sup> | ''k'' in A}. Por outro lado, todas linguagem unária tem uma versão binária mais compacta, o conjunto de codificações binárias de números naturais''k'' tal que 1<sup>''k''</sup> está na linguagem. |
O nome "unário" vem do fato de que uma língua unário é a codificação de um conjunto de [[números naturais]] no [[sistema de numeração unário]]. Como o universo das strings sobre qualquer alfabeto finito é um [[conjunto contável]], todas as linguagens podem ser mapeadas para um único conjunto A de números naturais, assim, cada linguagem tem uma ''versão unária'' {1<sup>''k''</sup> | ''k'' in A}. Por outro lado, todas linguagem unária tem uma versão binária mais compacta, o conjunto de codificações binárias de números naturais''k'' tal que 1<sup>''k''</sup> está na linguagem. |
||
Revisão das 02h03min de 29 de junho de 2015
 | Este artigo não cita fontes confiáveis. (Dezembro de 2013) |
 |
Esta página é parte de Wikipédia:Tradução de artigos e apresenta informações de toda a tradução deste artigo. Caso tenha dúvidas, veja Wikipédia Tradução: Como traduzir. |
Status da tradução Estágio 4 - Tradução completa
Autor do pedido Robertsonfilho (discussão)
Comentário Comentário aqui
Link permanente [URL date]
Interesse da tradução: importante contribuição para o estudo de informática teórica
Tradutor(es)
| Progresso da tradução | XX% |
Revisor(es)
| Progresso de revisão | XX% |
Em teoria da complexidade computacional, uma linguagem unária ou linguagem de registro é uma linguagem formal (um conjunto de strings), onde todas as strings têm a forma de 1k, onde "1" pode ser qualquer símbolo arbitrário. Por exemplo, a linguagem {1, 111, 1111} é unária, como é a linguagem {1k | k é primo}. A classe de complexidade de todas essas linguagens pode ser chamada de TALLY.
O nome "unário" vem do fato de que uma língua unário é a codificação de um conjunto de números naturais no sistema de numeração unário. Como o universo das strings sobre qualquer alfabeto finito é um conjunto contável, todas as linguagens podem ser mapeadas para um único conjunto A de números naturais, assim, cada linguagem tem uma versão unária {1k | k in A}. Por outro lado, todas linguagem unária tem uma versão binária mais compacta, o conjunto de codificações binárias de números naturaisk tal que 1k está na linguagem.
Como complexidade é normalmente medida em termos de tamanho da string de entrada, a versão unária da linguagem pode ser "mais fácil" que a linguagem original. Por exemplo, se a linguagem for reconhecível em tempo O(2n), sua versão unária pode ser reconhecida em tempo O(n), pois trocando cada simbolo por um "1" torana o tamanho da linguagem logaritmicamente menor. De forma mais geral, se uma linguagem pode ser reconhecida num tempo O(f(n)) e num espaçoO(g(n)), sua versão unária pode ser reconhecida num tempo O(n+f(logn)) e num espaço O(g(log n)) (nós requerimos um tempo O(n) só para ler a string de entrada). Entretanto, se o fato de ela pertencer ou não a uma linguagem é indecidível, então o fato de sua versão unária pertender ou não é indecidível também.