Algebraic Language

Let X be an alphabet (i.e., a finite and nonempty set), and call its member letters. A word on X is a finite sequence of letters a_1...a_n, where a_1,...,a_n in X. Denote the empty word by e, and the set of all words in X by X^*. Define the concatenation (also called product) of a word u=a_1...a_n with a word v=b_1...b_m as uv=a_1...a_nb_1...b_m. In general, concatenation is not commutative. Use the notation |u|_a to mean the number of letters a in the word u. A language L is then a subset of X^*, and L is said to be algebraic when a set of rewriting rules, applied recursively, forms all the words of L and no others.

See also

Dyck Language

Explore with Wolfram|Alpha


Bousquet-Mélou, M. "Convex Polyominoes and Algebraic Languages." J. Phys. A: Math. Gen. 25, 1935-1944, 1992.Delest, M.-P. and Viennot, G. "Algebraic Languages and Polyominoes [sic] Enumeration." Theoret. Comput. Sci. 34, 169-206, 1984.

Referenced on Wolfram|Alpha

Algebraic Language

Cite this as:

Weisstein, Eric W. "Algebraic Language." From MathWorld--A Wolfram Web Resource.

Subject classifications