Editing Formal language (section)

==Examples==

The following rules describe a formal language&nbsp;{{mvar|L}} over the alphabet Σ&nbsp;=&nbsp;{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:
* Every nonempty string that does not contain "+" or "=" and does not start with "0" is in&nbsp;{{mvar|L}}.
* The string "0" is in&nbsp;{{mvar|L}}.
* A string containing "=" is in&nbsp;{{mvar|L}} if and only if there is exactly one "=", and it separates two valid strings of&nbsp;{{mvar|L}}.
* A string containing "+" but not "=" is in&nbsp;{{mvar|L}} if and only if every "+" in the string separates two valid strings of&nbsp;{{mvar|L}}.
* No string is in&nbsp;{{mvar|L}} other than those implied by the previous rules.
Under these rules, the string "23+4=555" is in&nbsp;{{mvar|L}}, but the string "=234=+" is not. This formal language expresses [[natural number]]s, well-formed additions, and well-formed addition equalities, but it expresses only what they look like (their [[syntax]]), not what they mean ([[semantics]]). For instance, nowhere in these rules is there any indication that "0" means the number zero, "+" means addition, "23+4=555" is false, etc.

=== Constructions ===<!-- [[empty language]] redirects here -->
For finite languages, one can explicitly enumerate all well-formed words. For example, we can describe a language&nbsp;{{mvar|L}} as just {{mvar|L}}&nbsp;=&nbsp;{a, b, ab, cba}. The [[degeneracy (mathematics)|degenerate]] case of this construction is the '''empty language''', which contains no words at all (<span class="nounderlines">{{mvar|L}}&nbsp;=&nbsp;[[∅]]</span>).

However, even over a finite (non-empty) alphabet such as Σ&nbsp;=&nbsp;{a,&nbsp;b} there are an infinite number of finite-length words that can potentially be expressed: "a", "abb", "ababba", "aaababbbbaab",&nbsp;.... Therefore, formal languages are typically infinite, and describing an infinite formal language is not as simple as writing ''L''&nbsp;=&nbsp;{a, b, ab, cba}. Here are some examples of formal languages:
* {{mvar|L}} = Σ<sup>*</sup>, the set of ''all'' words over Σ;
* {{mvar|L}} = {a}<sup>*</sup> = {a<sup>''n''</sup>}, where ''n'' ranges over the natural numbers and "a<sup>''n''</sup>" means "a" repeated ''n'' times (this is the set of words consisting only of the symbol "a");
* the set of syntactically correct programs in a given programming language (the syntax of which is usually defined by a [[context-free grammar]]);
* the set of inputs upon which a certain [[Turing machine]] halts; or
* the set of maximal strings of [[alphanumeric]] [[ASCII]] characters on this line, i.e.,<br> the set {the, set, of, maximal, strings, alphanumeric, ASCII, characters, on, this, line, i, e}.