Notion Of Language

Let us remember a few definitions:

- a monoid is a set provided with an associative T binary operation admitting a neuter element. Let A = neuter element and XeA. Then, XTA = ATX = X

- a free monoid indicates that there is only a way to express an element XeA.

- starting from an alphabet X = {C,G,A,T...}, we call a language on X (all parts of the free monoid X*), every set of words on X.

3. Molecular Grammars

The basic question is how a computer program can judge if a sentence is grammatically correct or not. Chomsky proposed the mathematical concept of grammar to formalize this question (Chomsky 1963). At first, there is a mechanism (rules) which produces sentences (sets of words for natural language or sequence of symbols for biological problems). We can now wonder if a given sentence can be produced by the set rules.

So, this kind of grammar consists of a list of symbols and rules of transformation. In the case of the analysis of sequences, we wonder if it comes from a given grammar, that is from given rules of production. Parsing refers to grammatical analysis, to the action of searching for a derivation of the sequence from the grammar. There is also an alignment between the sequence and the grammar. In practice, Chomsky has defined four types of grammars:

- regular grammars

- context-free grammars

- context- sensitive grammars

- unrestricted grammars ('Turing's machine')

For genetic modeling, we are principally interested in regular and context-free grammars (see table I)

A molecular automaton with finite states is a kind of machine with several internal states and possibilities of transition from a state to another one according to rules of production (see HMM, but more general).

TABLE 1. Examples of grammars

Grammar type Regular Context-free (algebraic) Context-sensitive Unrestricted

Grammar example

Automata type w Aw

State finite automata w ^AwU+UwA+C wg+ gwc+d

State and pile automata w1^ACG+Aw2CG;

w2C^Cw2; w2G^w3CGG Cw3^w3C;Aw3^AA w2;Aw3^AA Turing machine

Turing machine