**Unary Language**
A unary language is a formal language over a single-symbol alphabet, typically consisting of strings made up of repeated occurrences of one symbol. It is often used in theoretical computer science and formal language theory to study computational complexity and automata behavior in simplified contexts.
## Definition
A unary language is a subset of strings over a unary alphabet, usually denoted as {1} or {a}, where each string is composed of one repeated symbol. For example, the language L = {1^n | n is a prime number} is a unary language containing strings of length equal to prime numbers.
## Properties and Applications
Unary languages are significant in computational theory because they simplify the structure of strings, allowing researchers to focus on length-based properties rather than symbol diversity. They are used to analyze decision problems, complexity classes, and automata with restricted alphabets. Unary languages often serve as benchmarks for understanding the complexity of problems when input size is encoded in unary rather than binary.
## Computational Complexity
Encoding inputs in unary can affect the complexity classification of problems. Some problems that are hard in binary encoding become easier or fall into different complexity classes when inputs are given in unary. This is because unary encoding inflates input size, impacting time and space requirements for algorithms.
—
**Meta Description:**
A unary language is a formal language over a single-symbol alphabet, used in theoretical computer science to study computational complexity and automata. It consists of strings formed by repeated occurrences of one symbol.