Linguagem unária: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Página marcada como sem fontes, usando FastButtons. |
Erro ortográfico |
||
Linha 48:
__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
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.
| |||