Formal language

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.