Editing Formal language (section)

== Words over an alphabet ==
{{main article|Alphabet (formal languages)}}
An ''alphabet'', in the context of formal languages, can be any [[set (mathematics)|set]]; its elements are called ''letters''. An alphabet may contain an [[countable set|infinite]] number of elements;{{NoteTag|For example, [[first-order logic]] is often expressed using an alphabet that, besides symbols such as ∧, ¬, ∀ and parentheses, contains infinitely many elements ''x''<sub>0</sub>,&nbsp;''x''<sub>1</sub>,&nbsp;''x''<sub>2</sub>,&nbsp;… that play the role of variables.}} however, most definitions in formal language theory specify alphabets with a finite number of elements, and many results apply only to them. It often makes sense to use an [[alphabet]] in the usual sense of the word, or more generally any finite [[character encoding]] such as [[ASCII]] or [[Unicode]].

A '''word''' over an alphabet can be any finite sequence (i.e., [[string (computer science)|string]]) of letters. The set of all words over an alphabet Σ is usually denoted by Σ<sup>*</sup> (using the [[Kleene star]]). The length of a word is the number of letters it is composed of. For any alphabet, there is only one word of length 0, the ''empty word'', which is often denoted by e, ε, λ or even Λ. By [[concatenation]] one can combine two words to form a new word, whose length is the sum of the lengths of the original words. The result of concatenating a word with the empty word is the original word.

In some applications, especially in [[logic]], the alphabet is also known as the ''vocabulary'' and words are known as ''formulas'' or ''sentences''; this breaks the letter/word metaphor and replaces it by a word/sentence metaphor.