Linguagem unária

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 1^k, onde "1" pode ser qualquer símbolo arbitrário. Por exemplo, a linguagem {1, 111, 1111} é unária, como é a linguagem {1^k | 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 {1^k | 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 1^k 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.