Formal language

Language

Examples

Some examples of formal languages:

• the set of all words over ${\displaystyle {a,b}\,}$
• the set ${\displaystyle \left\{a^{n}\right\}}$, where ${\displaystyle n\,}$ is a natural number and ${\displaystyle a^{n}\,}$ means ${\displaystyle a\,}$ repeated ${\displaystyle n\,}$ times
• finite languages, such as ${\displaystyle \{\{a,b\},\{a,aa,bba\}\}\,}$
• the set of syntactically correct programs in a given programming language; or
• the set of inputs upon which a certain Turing machine halts.

Specification

A formal language can be specified in a great variety of ways, such as: