Namespaces
Variants
Actions

Formal language

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


in mathematical linguistics

An arbitrary set of chains (that is, words, cf. Word) over some (finite or infinite) alphabet $ V $( sometimes also called a dictionary), that is, a set of expressions of the form $ \omega = a _ {1} \dots a _ {k} $, where $ a _ {1} \dots a _ {k} \in V $; the number $ k $, usually denoted by $ | \omega | $, is the length of the chain $ \omega $. One also considers the empty chain, denoted by $ \Lambda $; one sets $ | \Lambda | = 0 $. One often speaks of a language over the alphabet $ V $, omitting the word "formal" . In mathematical linguistics and the theory of automata (cf. Automata, theory of) one considers various effective ways of specifying a formal language, principally by means of formal grammars (cf. Grammar, formal) and automata of various types, which can, in the majority of cases, be described as modifications of non-deterministic Turing machines (cf. Turing machine), often multi-tape, with some restrictions on the ways the machine works on each tape.

Operations on formal languages.

In addition to the usual set-theoretic operations on formal languages, one carries out: multiplication (or direct multiplication, or concatenation):

$$ L _ {1} L _ {2} = \ \{ {xy } : {x \in L _ {1} , y \in L _ {2} } \} ; $$

left division:

$$ L _ {2} \setminus L _ {1} = \ \{ {x } : {\exists y, z ( y \in L _ {1} \& z \in L _ {2} \& y = zx) } \} ; $$

right division $ L _ {1} /L _ {2} $ is defined by analogy with left division; iteration:

$$ L ^ {*} = L ^ {0} \cup L ^ {1} \cup \dots , $$

where $ L ^ {0} $ denotes $ \{ \Lambda \} $ and $ L ^ {n + 1 } = L ^ {n} L $( in particular, the set of all chains in $ V $ is $ V ^ {*} $); truncated iteration:

$$ L ^ {+} = L ^ {1} \cup L ^ {2} \cup \dots ; $$

and substitution: If $ L $ is a language over the finite alphabet $ \{ a _ {1} \dots a _ {n} \} $ and $ L _ {1} \dots L _ {n} $ are arbitrary languages, then

$$ S ( L; a _ {1} \dots a _ {n} \mid L _ {1} \dots L _ {n} ) = $$

$$ = \ \{ x _ {i _ {1} } \dots x _ {i _ {k} } : \ a _ {i _ {1} } \dots a _ {i _ {k} } \in L \& x _ {i _ {1} } \in L _ {i _ {1} } \& \dots \& x _ {i _ {k} } \in L _ {i _ {k} } \} ; $$

if each of the languages $ L _ {i} $, $ i = 1 \dots n $, consists of one chain $ z _ {i} $, a substitution is called a homomorphism; if all the $ z _ {i} $ are non-empty, one speaks of an unabbreviated homomorphism. If the language $ \{ x \} $ consists of one chain $ x $, then instead of $ \{ x \} L $, $ \{ x \} \setminus L $, etc., one writes $ xL $, $ x \setminus L $, etc., respectively.

A variety of languages is an ordered pair $ ( {\mathcal E} , {\mathcal L} ) $( or $ {\mathcal L} $, if $ {\mathcal E} $ is taken for granted), where $ {\mathcal E} $ is an infinite alphabet and $ {\mathcal L} $ is a class of languages such that: 1) for every $ L \in {\mathcal L} $ there is a finite alphabet $ \Sigma \subset {\mathcal E} $ such that $ L \subset \Sigma ^ {*} $; 2) $ L \neq \emptyset $ for some $ L \in {\mathcal L} $; and 3) $ {\mathcal L} $ is closed relative to union, multiplication, intersection with regular sets, truncated iteration, unabbreviated homomorphisms, and inverses of arbitrary homomorphisms. A variety that is closed relative to arbitrary homomorphisms is called complete.

References

[1] A.V. Gladkii, "Formal grammars and languages" , Moscow (1973) (In Russian)
[2] S. Ginsburg, S. Greibach, Y. Hopcroft, "Studies in abstract families of languages" Mem. Amer. Math. Soc. , 87 (1969) pp. 1–32

Comments

For more details see Formal languages and automata.

How to Cite This Entry:
Formal language. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Formal_language&oldid=46955
This article was adapted from an original article by A.V. Gladkii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article