Mathematical concept for formal languages

Question

A formal language is defined as a subset of finite-length strings over an alphabet. It is similar to the mathematical concept "relation", but the lengths of its strings are not fixed.

Since the name "formal language" suggests its application to linguistics, I wonder if there is a pure mathematical concept/name for "formal languages"?

Are there applications of formal languages that are not used to model languages (either natural languages or computer languages)?

Thanks!

Answer 1

Your question is not completely clear.

This is the mathematical definition of Formal language :

A formal language $\mathcal L$ over an alphabet $\Sigma$ is a subset of $\Sigma^*$ [see Kleene star], that is, a set of words over that alphabet. Sometimes the sets of words are grouped into expressions, whereas rules and constraints may be formulated for the creation of 'well-formed expressions'.

While formal language theory usually concerns itself with formal languages that are described by some syntactical 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 nor less. In practice, there are many languages that can be described by rules, such as regular languages or context-free languages. The notion of a formal grammar may be closer to the intuitive concept of a "language," one described by syntactic rules.

Having said that, what are you meaning with "a pure mathematical concept/name of 'formal languages' " ?

Answer 2

There is nothing un-mathematical about the definition, but there is an algebraic translation.

Formal power series of non-commuting variables are a natural generalization of formal languages. Let $K$ be a semiring. (This is a ring without the additive inverse requirement.) Let $A$ be a set and $A^*$ be the free monoid generated by $A$. A formal power series $S$ is a function $A^* \rightarrow K$. The image of a word $w$ is called the coefficient of $w$ in $S$. Addition and multiplication of series are defined as one would expect.

In this setting, a formal language $\mathcal{L}$ can be defined as a formal power series (of non-commuting variables) whose coefficients are either $0$ or $1$. The words in $A^*$ with coefficient $1$ are interpreted as the ones in $\mathcal{L}$.

One application of this approach is to enumerate a combinatorial class of objects. If a class of objects are in bijection with a formal power series in non-commuting variables, we obtain a generating function for the objects of size $n$ by substituting $x$ for each of the other variables.

We expect there to be some relationship between the type of generating function (rational, algebraic, etc) of a class of objects and the type of language it arises from. This situation is described in the introduction of Bousquet-Melou's "Rational and algebraic series in combinatorial enumeration", found here.

More about this approach to enumeration can be found in Chapter 6 of Richard Stanley's "Enumerative Combinatorics Volume 2". Also, the book "Rational Series and Their Languages" by Berstel and Reutenauer is a good reference for the formal series connection to languages, even though the focus is on rational languages.