Editing Formal language (section)

=== 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}.