Editing Formal language (section)

==Definition==
Given a non-empty set <math>\Sigma</math>, a '''formal language <math>L</math> over <math>\Sigma</math>''' is a [[subset]] of <math>\Sigma^*</math>, which is the set of [[Kleene_star|all possible finite-length words over <math>\Sigma</math>]]. We call the set <math>\Sigma</math> [[alphabet (formal languages)|'''the alphabet of <math>L</math>''']]. On the other hand, given a formal language <math>L</math> over <math>\Sigma</math>, a word <math>w \in \Sigma^*</math> is ''well-formed'' if <math>w\in L</math>. Similarly, an expression <math>E\subseteq\Sigma^*</math> is ''well-formed'' if <math>E\subseteq L</math>. Sometimes, a formal language <math>L</math> over <math>\Sigma</math> has a set of clear rules and constraints for the creation of all possible well-formed words from <math>\Sigma^*</math>.

In computer science and mathematics, which do not usually deal with [[natural language]]s, the adjective "formal" is often omitted as redundant. On the other hand, we can just say "a formal language <math>L</math>" when its alphabet <math>\Sigma</math> is clear in the context.

While formal language theory usually concerns itself with formal languages that are described by some syntactic rules, the actual definition of the concept "formal language" is only as above: a (possibly infinite) set of finite-length strings composed from a given alphabet, no more and no less. In practice, there are many languages that can be described by rules, such as [[regular language]]s or [[context-free language]]s. The notion of a [[formal grammar]] may be closer to the intuitive concept of a "language", one described by syntactic rules. By an abuse of the definition, a particular formal language is often thought of as being accompanied with a formal grammar that describes it.