Grammaire compilée |
Automate déterministe |
| `{B,C}` `B → a{C,D}` `C → c{B,C}"|"bE"|"ε` `D → bB` `E → aB` `{C,D} → c{B,C}"|"b{B,E}"|"ε` `{B,C} → a{C,D}"|"c{B,C}"|"bE"|"ε` `{B,E} → a{B,C,D}` `{B,C,D} → a{C,D}"|"c{B,C}"|"b{B,E}"|"ε` |
 |
Les langues écrites utilisent un alphabet fini et leurs mots se résument en des séquences de caractères appartenant à cet alphabet. C'est ainsi que l'on définie les langages formels, appelé aussi langage de caractères.
Etant donné un alphabet `A = {a,b,c}`. Le langage mère d'alphabet `A` se note `A"*"`. C'est l'ensemble des mots qu'il est possibles d'écrire dans cet alphabet et auquel on ajoute un mot particulier qu'est le mot vide noté `ε`.
`A = {a, b, c}`
`A"*" = {ε, a, b, c, aa, ab, ac, ba, b\b, bc, ca, cb, c\c, aaa, aab,...}`
Ainsi, les mots du langage mère sont les séquences finies de caractères appartenant à l'alphabet. Et la séquences vide se note `ε` et s'appelle le mot vide.
On ne fait pas de distinction entre un caractère et la séquence singleton le contenant. De telle sorte que `A"⊂"A"*"` et que `A"*"` constitue la clôture de `A` par concaténation et par ajout du mot vide `ε`. Le suffixe `"*"` est l'opérateur de Kleene qui procède à cette clôture.
Un langage `L` d'alphabet `A` est par définition un sous ensemble du langage mère `A"*"`. La seul contrainte que nous nous fixons dans cette terminologie, est que l'alphabet `A` doit être fini.
Les langages de caractères semblent d'apparence plus simple que les langages d'opérateurs, les mots étant simplement des séquences de caractères. Mais les structures se définissent en termes d'opérateurs, rendant explicite l'opération de construction des mots. Et il y a deux façons de percevoir une telle construction : soit en utilisant l'opérateur binaire de concaténation, soit en utilisant seulement des opérateurs unaires.
La structure de `A"*"` comprend des éléments générateurs que sont les caractères de l'alphabet, un élément générateur particulier qu'est `ε`, et un opérateur binaire générateur qu'est la concaténation et que l'on note `"∗"`.
Pourtant le symbole `"∗"` n'apparait pas dans l'expression des mots. En effet c'est une opération abstraite qui apparait dans notre façon de voir. L'opération de concaténation existe et elle est nécessaire pour construire les éléments de la structure appelés mots. Si nous la rendons explicite, nous obtenons :
`A"*" = {ε, a, b, c, a"∗"a, a"∗"b, a"∗"c, b"∗"a, b"∗"b, b"∗"c, c"∗"a, c"∗"b, c"∗"c, a"∗"a"∗"a, a"∗"a"∗"b,...}`
Mais il est plus pratique de noter l'opération de concaténation par absence de symbole entre deux caractères ou mots. Cela constitue une règle syntaxique. Dans ce cas, une expression telle que `aεbε` sera interprétée comme `a"∗"ε"∗"b"∗"ε`, et sera égale à `a"∗"b` et finalement à `ab`.
La présentation de la structure est la suivante :
`A"*" = "<"ε, a, b, c, "∗(.,.)>" "/" {"∗"` est associatif, `ε` est l'élément neutre de `"∗"}`
`{"∗"` est associatif`} <=> {∀x∀y∀z, (x"∗"y)"∗"z "=" x"∗"(y"∗"z)}`
`{ε` est l'élément neutre de `"∗"} <=> {∀x, ε"∗"x "=" x, x"∗"ε"="x}`
Sa présentation en notation programmative peut s'écrire comme suit (voir Structures fondamentales) :
`A"*" = `Monoïde trigène `("∗", ε, a,b,c)`
L'ensemble `A` est l'alphabet fini qui engendre le monoïde `A"*"`. Le nom du patron change selon le nombre de caractères contenus dans l'alphabet. On parlera de Monoïde bigène `("∗",ε,a,b)`, de Monoïde trigène `("∗",ε, a,b,c)`, etc.. Comme il n'y a pas de règle d'égalité supplémentaire ces structures sont qualifiées de libre. Le langage libre d'alphabet `A` est le monoïde libre engendré par `A`, et se note `A"*"`.
Si on enlève l'élément ε, on obtient une structure plus simple notée `A^+ = A"*""-"{ε}` de présentation et programmative suivante :
`A^+ = "<"a, b, c, "∗(.,.)>" "/" {"∗"` est associatif`}`
`A^+ = `Semi-groupe trigène `("∗",a,b,c)`
Notez que l'on peut toujours rajouter un élément neutre à un semi-groupe. Voici une autre notation autorisée de la présentation et programmative, où l'alphabet `A` est un ensemble fini :
`A"*" = "<"ε, "@"A, "∗(.,.)>" "/" {"∗"` est associatif, `ε` est l'élément neutre de `"∗"}`
`A"*" = `Monoïde de type fini `("∗", ε, A)`
où `"@"A` doit être remplacé par la séquence des éléments de `A`. Puis voici une autre notation, si on se place sous un patronage telle que celui de monoïde, alors les présentations ne mentionneront pas l'opération binaire interne de la structure ni son élément neutre et ne mentionneront pas la théorie de la structure qui sera celle du monoïde admise implicitement. L'opération binaire sera notée par `"∗"` ou par absence de symbole, et l'élément neutre sera noté par `1`. Par exemple, considérons la présentation suivante sous le patronage de monoïde :
`"<"a,b,c">" "/" {ab"="ba, abc"="c, c\c"="1}`
Cette présentation correspondra à la présentation complète suivante :
`"<"1, a, b, c, "∗(.,.)>" "/" {"∗"` est associatif, `1` est l'élément neutre de `"∗"`, `ab"="ba`, `abc"="c`, `c\c"="1}`
Et il faudra traduire, l'opération `"∗"` correspondant à la concaténation, et l'élément `1` correspondant au mot vide `ε`.
Mais il existe une autre façon de définir les monoïdes, jugée plus simple, puisque n'utilisant que des opérateurs unaires et aucun opérateur binaire. Au lieu de considérer une opération d'assemblage binaire `"∗(.,.)"`, on considère les caractères comme étant des opérateurs unaires, appellés aussi des applications unaires, formant ainsi des objects enfichables les uns dans les autres pour former des mots, et eux-mêmes constituant des mots. La structure se présente alors comme l'ensemble des applications unaires engendrées à partir des trois applications unaires `a"(.)"` et `b"(.)"` et `c"(.)"`, ce qui se note par `"<"a"(.)", b"(.)", c"(.)>"_1` où l'indice `1` indique que l'on s'intéresse à l'ensemble des applications unaires engendrées. Puis l'ajout de `ε` revient à ajouter l'identité `ε = (x|->x)`.
Vous remarquerez que l'ensemble sous-jacent sur lequel opèrent toutes ses applications n'est pas mentionné. On verra plus tard qu'il existe un ensemble sous-jacent canonique de construction assez simple et suffisament riche pour que toutes les aplications engendrées par ce procédé soient réellement distinctes en tant qu'application sur cet ensemble.
Comme il n'y a pas de règle d'égalité supplémentaire ces structures sont qualifiées de libre.
Prenons quelques caractères : `a, b, c`, et regroupons-les dans un ensemble `A={a,b,c}` appelé alphabet. Le langage mère noté `A"*"` en est la clôture par concaténation et par ajout du mot vide. :
`A"*" = {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba....}`
C'est l'ensemble de tous les mots composés de caractères de l'alphabet `A` auquel on a ajouté le mot vide noté `ε`. Le signe `"*"` est l'opérateur de Kleene. Il désigne la cloture par concatenation avec ajout du mot vide `ε`. Le mot vide n'est constitué d'aucun caractère. C'est une séquence vide représentée par le symbôle `ε`. Noter alors que `ε` est un mot et n'est pas un caractère. Il ne fait pas partie de l'alphabet `A`.
On code les `n` caractères de l'alphabet `A` par les entiers de `1` à `n`. Puis on code les mots de `A"*"` selon le développement en base `n` selon l'endianess big-endian (gros bout d'abord) :
Le mot vide `ε` a un code égale à zéro. Le mot d'un seul caractère a un code égal à celui du caractère. Le mot à deux caractères a comme code la somme du code du premier caractère (celui le plus à gauche) multplié par `n^2`auquel on ajoute le code du second caractère (celui le plus à droite).
Si l'alphabet est composé de n caractères `a,b,c,...`, codés comme suivant : `a"="1`, `b"="2`, `c"="3`, ... , le code d'un mot correspond au développement big-endian en base n. Par exemples :
Le mot `abc` possède comme code `1n^2 + 2n + 3`
Le mot `bacb` possède comme code `2n^3 + 1n^2+ 3n + 2`
L'odre définie par ce codage respecte l'ordre de la taille des mots.
Ce codage est une bijection entre `A"*"` et `NN`. Autrement, il constitue un algorithme de compression maximal, on ne peut pas comprimer davantage l'information.
La représentation décimale des entiers se fait en prenant comme alphabet `A = {0,1,2,3,4,5,6,7,8,9}` et en les codant dans cet ordre `1,2,3,4,5,6,7,8,9,10` et en choississant le développement en base 10 selon l'indianess big-endian.
Dans le cas général, une règle de production va utiliser des connaissances déjà acquises, pour en produire d'autres selon un processus calculatoire. Les connaissances ainsi produites sont dites introspectives. On remarque qu'une règle de démonstration correspond finalement à une telle règle de production. C'est pourquoi on utilise comme symbole de production, le symbole de démonstration `"⊢"`. Et c'est pourquoi un ensemble fini de telles règles constitue une théorie.
Nous allons d'abord nous intéresser à des règles unaires de production finie, c'est à dire ne transformant qu'un mot à la fois et ne produisant qu'un nombre fini de mots à la fois.
Nous allons définir des tranformations possédant des quantités effectives de calcul que nous mesurerons.
Puis on s'intéressera à des règles de productions particulièrement simples que sont les règles de réécriture.
Puis ces règles étant elle-mêmes constituées de caractères, on regardera comment agrandire le langage pour les incorporer comme des mots.
Une règle unaire de production finie est une application calculable de `A"*"→ ccP_"fini"(A"*")`. Soit `r` une telle règle, et soit `m` un mot, il existe donc un nombre fini `n` de mots `m_1,m_2,m_3,...,m_k` résultats de l'application de la règle `r` sur le mot `m`, ce qui se note :
`r(m) = {m_1,m_2,m_3,...,m_k}`
Notez bien que chacun des mots `m_1,m_2,m_3,...m_k` est obtenue en appliquant une seul fois la règle `r` sur le mot `m`.
Un ensemble de mots s'appelle un langage. Un ensemble fini `R` de règles unaires de production finie constitue encore une règle unaire de production finie :
`R(x) = uuu_(r in R) r(x)`
En étendant la notation applicative aux ensembles, la règle unaire `R` s'applique à un ensemble de mots, `L` :
`R(L) = uuu_(x in L) R(x)`
Le mécanisme de production de mots obtenu en appliquant successivement deux règles de `R` à l'ensemble `L` constitue encore une règle unaire de production finie que l'on note `R^2` :
`R^2(L) = R(R(L))`
De même, le mécanisme de production de mots obtenu en appliquant successivement `n` règles de `R` à l'ensemble `L` constitue encore une règle unaire de production finie que l'on note `R^n` :
`R^n(L) = obrace(R"("R"("..."("R)^(n" termes") (L) ")"`
Parcontre, le mécanisme de production de mots obtenue en appliquant successivement un nombre fini quelconque de règles de `R` à l'ensemble `L` constitue une règle unaire qui n'est plus de production finie en règle générale. On la note `R"*"`. Notez que par convention `R^0` représente l'identité `R^0(L)=L`.
`R"*"(L) = uuu_(ninNN)obrace(R"("R"("..."("R)^(n" termes") (L) ")"`
Cet ensemble représente toute les déductions possibles de `L" et "R`.
Notez qu'il n'y a pas de différence entre une règle unaire de production finie et un ensemble fini de règles unaires de production finie. Considérons l'expression suivante :
`L |--_R^n E`
Cette expression signifie que les mots de `E` s'obtiennent en appliquant `n` règles successives de `R` à l'ensemble `L`. Considérons l'expression suivante :
`L |--_R E`
Cette expression signifie que les mots de `E` s'obtiennent en appliquant un nombre fini quelconque de règles successives de `R` à l'ensemble `L`.
Et dans ces deux expressions, les ensembles `L,R,E` peuvent être remplacés par des éléments qui seront délors chacun concidéré comme l'ensemble singleton le contenant.
Remarquez que `R` appartient à `A"*"→ ccP_"fini"(A"*")` et que `L` appartiennent à `ccP(A"*")`.
L'ensemble de toutes les productions possibles de mots à partir de `L` en appliquant la règle `R` un nombre quelconque de fois se note `R"*"(L)`. Cet ensemble se partitionne selon le niveau de complexité de déduction comme suit :
`R"*"(L) = L + (R(L)"\"L) +(R^2(L)"\"(R(L)uuL)) + (R^3(L)"\"(R^2(L)uuR(L)uuL))+...`
Quelque soit un mot `x` de `R"*"(L)`, le niveau de complexité de déduction de `x` à partir de `L` avec la règle unaire `R` se note :
`"niv"_(L,R)(x) = min{i "/" L|--_R^i x }`
Une règle unaire `R` sera dite inférieur ou égale à une règle unaire `S` et on notera `R"⩽"S` , si et seulement si lorsqu'elles s'appliquent à un mot quelconque du langage mère `A"*"`, tout ce que peut produire `R` est produit pas `S`.
`R"⩽"S <=> AAm"∈"A"*", R(m)"⊆"S(m)`
On remarquera que cette définition est équivalente à celle-i :
`R"⩽"S <=> AAL"∈"ccP_(⩾1)(A"*"), R(L)"⊆"S(L)`
Où `ccP_(⩾1)` désigne l'ensemble des partie non vides. Notez il n'y a pas de différence entre une règle unaire de production finie et un ensemble fini de règles unaires de production finie. Et donc, si un ensemble de règles possède une règle inférieure à l'ensemble des autres règles, alors elle peut être enlevée sans que cela ne modifie le langage engendré ni la complexité de déduction de ses mots.
Une règle de réécriture s'applique à un mot. Elle effectue une recherche d'occurrence de séquence dans ce mot, et produit le mot transformé en lui substituant une et une seul occurrence trouvée. La règle est constituée de deux mots appartenant à `A"*"` que l'on note séparés par le symbôle `"→"`. Autrement dit, l'ensemble des règles est :
`A"*"^2`
La règle appliquée à un mot, produit un ensemble fini de mots, autant qu'il y a d'occurrences rencontrées dans le mot correspondant au premier terme de la règle, et qui sera substitué par le second terme de la règle. S'il n'y a aucune occurrence, la règle retourne l'ensemble vide.
Par exemple, la règle `ab"→"ba` appliquée au mot `abab` produira exactement les deux mots `baab` et `ab\ba`, ce qui s'écrit :
`(ab"→"ba)(abab) = {baab, ab\ba}`
Si le premier terme de la règle est le mot vide, tel que par exemple la règle `ε"→"ab`, alors cela signifie que l'on peut insérer la séquence `ab` en tout endroit du mot sur lequel s'applique la règle. Exemple :
`(ε"→"d)(abc) = {dabc,adbc,abdc,abcd}`
Lorsque plusieurs règles ont le même premier membre, on les réunie en une seule règle produisant autant de mots séparés par le symbôle `|` qui dénote l'alternative. Par exemple la règle : `ab"→"c|aa|ba` correspond à l'ensemble de règles suivantes `{ab"→"c``, ab"→"aa``, ab"→"ba}`. Appliquée au mot `aab`, elle produit les mots `{ac, aaa, aba}`.
`ab"→"c|aa|ba = {ab"→"c, ab"→"aa, ab"→"ba}`
Par exemple :
`(ab"→"c|aa|ba)(aab)= {ac, aaa, aba}`
Une théorie prélogique est un ensemble fini regroupant des mots et des règles de production. On s'intéresse ici à une forme particulière de théorie dite de réécriture.
Une théorie `T` de réécriture est un ensemble fini regroupant des mots appartenant à `A"*"` et des règles de réécriture appartenant à `A"*"^2`. Notez qu'une règle de réécriture est une règle unaire de production finie. Par exemple :
` T = {{:(a),(abc), (a"→"bc), (b\b"→"caa), (bcb"→"ε), (cbc"→"a):}}`
La théorie se décompose en deux ensembles, l'ensemble `T_0` regroupant les mots appartenant à `T`, et l'ensemble `T_1` regroupant les règles de réécriture appartenant à `T` :
`T =T_0 uu T_1`
`T_0 = {a,abc}`
`T_1 ={a"→"bc, b\b"→"caa, bcb"→"ε, cbc"→"a}`
La théorie `T` engendre un langage qui est l'ensemble de tous les mots qu'elle déduit et que l'on note `"<"T">"`. Nous avons :
`"<"T">" = T_1"*"(T_0)`
`"<"T">" = uuu_(n in NN) T_1^n(T_0)`
Et nous avons :
`T_0={a,abc}`
`T_1(T_0)" = {bc, bcbc}`
`T_1^2(T_0)" = {c, ba}`
`T_1^3(T_0)" = {b\bc}`
`T_1^4(T_0)" = {caac}`
`T_1^5(T_0)" = {cbcac, cabc\c}`
`T_1^6(T_0)" = {cbcbc\c, aac}`
`T_1^7(T_0)" = {bcac, abc\c, c\c\c, cbac}`
`T_1^8(T_0)" = {bcbc\c, cb\bc\c}`
`T_1^9(T_0)" = {c\caac\c, c\c, bac}`
`...`
`"<"T">" = {a,abc,bc,bcbc,c,ba,b\bc,caac,cbcac,cabc\c,cbcbc\c, aac, bcac, abc\c, c\c\c, cbac, bcbc\c, cb\bc\c,...}`
Une théorie `U` sera dite inférieure ou égale à une théorie `V` et on notera `U"⩽"V`, si et seulement si `"<"U">"sube"<"V">"` :
`U"⩽"V <=> "<"U">" sube "<"V">"`
Une théorie `T` sera dite incohérente si et seulement si elle engendre tous les mots :
`T " incohérent" <=> "<"T">"=A"*"`
Etant donné une théorie de réécriture `T`, il est possible de procéder à des calculs de règles supplémentaires, ce qui aura pour effet de diminuer le niveau de complexité de déduction des mots.
Un première méthode de construction de règles consiste à appliquer une règle sur le second terme d'une règle pour produire une nouvelle règle. Par exemple :
`(ba"→"c)(ab"→"bac)= ab"→"c\c`.
Et il convient aussi de supprimer les règles `r` inférieures ou égales à une autre règles `s` présente, c'est à dire tel qu'il existe `(u,v)"∈"A"*"` tel que `r_1"="us_1v` et `r_2"="us_2v`.
`r"⩽"s <=> EE(u,v)"∈"A"*", ur_1v"="s_1" et "ur_2v"="s_2`
Si on met en oeuvre ce mécanisme de construction de règle et de suppression de règle, alors le niveau de complexité de déduction des mots produit diminura.
La règle de réécriture constitue une demi-règle d'égalité entre deux mots, en permettant de substituer l'un par l'autre, ou bien de faire cette substitution à l'interieur d'un mot comme sous-mot. Mais la substitution n'est aurorisé que dans un sens donné.
Un lien étroit s'opère entre la théorie de réecriture qui regroupe l'ensemble des règles de réécriture choisies, et la présentation du monoïde qui regroupe l'ensemble des règles d'égalités choisies, à ceci près que l'égalité fonctionne dans les deux sens alors que la règle de réécriture ne fonctionne que dans un sens. Voyez par exemple, ces deux structures sont équivalentes :
`b`
`c`
`ab"→"ba`
`ba"→"ab`
`abc"→"c`
`c"→"abc`
`ε"→"c\c`
`c\c"→"ε`
Un monoïde est présenté habituellement en notation multiplicative, et donc le `1` désigne l'élément neutre c'est à dire ici le mot vide `ε`.
Ainsi la théorie de réécriture constitue une structure plus générale que celle de monoïde. Une règle de réécriture correspond à une demi-règle d'égalité munie d'un sens. Toutes deux font partie du langage des propositions pour une théorie de réécriture. Les règles de réécritures enrichissent le langage des propositions des monoïdes, et font partie d'un langage des propositions plus riches qui est celui des théories de réécriture. Par exemple, nous avons :
`{ab"→"ba, ba"→"ab} <=> {ab"="ba}`
Les mots du langages peuvent être vus comme des propositions logiques. Leur signification se mesure alors dans un univers des mondes possibles. C'est l'approche platonicienne de la vérité décrite par l'allégorie de la caverne où les hommes sont enchainés et ne perçoivent que des ombres qui résultent du monde exterieur inconnue et qui désignent des propriétés de ces mondes. La proposion est vrai dans certains mondes, et en mathématique classique qui définit la négation comme une symétrie parfaite, la proposion est fausse dans les autres mondes. Les mondes s'appellent des modèles. Et la théorie qui décrit ces mondes possibles s'appelle la théorie des modèles.
Les règles de production sont comme des règles de déduction. Le choix d'un système de déduction détermine la sémantique c'est à dire le sens des propositions logiques que le système de déduction manipule, c'est à dire ici le sens des mots du langage.
Un élément qui peut être un mot ou une règle de réecriture constitue une proposition (ou propriété). Le langage des propositions (ou langage des propriétés) pour les théories de réécritures, est donc `A"*" + A"*"^2`.
Pour augmenter le pouvoir d'expression des théories de réécriture, on veut utiliser des variables. On remarque qu'il n'y a pas de différence entre une variable et un nouvel élément que l'on rajoute, sachant qu'il peut être égal à tout mot du langage `A"*"` ou constituer vraiment un nouvel élément, un nouveau mot et donc dans ce cas, nécessairement constituer un nouveau caractère. C'est ce que l'on appelle une extension élémentaire de la structure de monoïde `A"*"`.
Ainsi il n'y a pas de différence conceptuel entre une variable et un nouvel élément ajouté à la structure de monoïde `A"*"` par extension élémentaire.
On ajoute à l'alphabet `A` des symboles supplémentaires notés `X,Y,Z,...` L'ensemble des symboles se note `S"="{X,Y,Z,...}`. Ces symbôles vous servir de variables, mais se ne sont pas des variables telle qu'on a l'habitude de les concevoir. Ce sont des caractères rajoutés à l'alphabet, c'est )à dire une extension élémentaire de la structure de monoïde libre, passant de `A"*"` à `(A+S)"*"`.
Et chaque symbole de `S` désignera un sous-langage.
Par convention, `A"*"` sera l'ensemble des mots c'est à dire le langage, `(A+S)"*"` sera l'ensemble des méta-mots, `(A+S)"*"^2` sera l'ensemble des règles, L'ensemble des propositons (ou propriétés) sera l'union de l'ensemble des méta-mots et de l'ensemble des règles, et constitura le méta-langage.
Une grammaire générale peut être vue comme une règle unaire de production, énumérant les mots d'un langage.
La grammaire se présente formellement sous forme d'un quadruplet comprenant :
Considérons par exemple la grammaire suivante :
`(A,S,M,R) = ({a,b}, {X,Y}, {Y, XaY}, {aX"→"Yb, Y "→"aY|Xb|ε})`
Mais on préfère présenter la grammaire sous la forme d'une théorie, la théorie `T = D + R` , où `D` regroupe les propositions écrites en un seul méta-mot et `R` regroupe les propositions écrites en deux méta-mots. Et il convient de définir préalablement l'alphabet étendu `A + S` comprenant caractères et symboles, ou plus simplement de choisire préalablement un moyen de les différentier. On choisie pour cela la casse du caractère ; les caractères terminaux sont en minuscules et les symboles ou caractères non terminaux sont en majuscules. La grammaire constitue une théorie de réecriture écrite dans un alphabet étendu.
`T ={{:(Y),(XaY),(aX"→"Yb),(Y"→"aY|Xb|ε):}}`
La grammaire est un processus de construction de mots. A partir de quelques mots initiaux, ici `Y` et `XaY`, et de quelques règles initiales, ici `aX"→"Yb` et `Y"→"aY|Xb|ε`, la grammaire engendre deux langages ; un langage étendu, d'alphabet `A"+"S`, et un langage d'alphabet `A` contenant seulement les mots dits terminaux.
Voici un exemple d'utilisation d'une grammaire pour décrire les expressions arithmétiques :
`A = {"+","∗","(",")",0,1,2,3,4,5,6,7,8,9,}`
`S = {E,N,C}`
`D = {E}`
`R = {{: ( E->E"+"E "|" E"∗"E "|" "("E")" "|" N),(N->CN "|" C),(C->0 "|" 1 "|" 2 "|" 3 "|" 4 "|" 5 "|" 6 "|" 7 "|" 8 "|" 9):}}`
Le symbole `E` représente une expression arithmétique, donc désigne le langage des expressions arithmétiques.
Le symbole `N` représente un nombre, donc désigne le sous-langage des nombres.
Le symbole `C` représente un chiffre, donc désigne le sous-langage des chiffres.
L'ordre des productions d'une règle appliquée à un mot correspond à l'ordre de rencontre de chaque occurence dans le mot de gauche à droite, en ne remplaçant à chaque fois qu'une seul occurence. Pour remplacer 2 occurences il faudra appliquer successivement 2 fois la règle. L'ordre des productions d'une liste de règles appliquée à une liste de mots consiste à appliquer une fois la première règle à chacun des mots dans l'ordre de la liste, puis d'appliquer la deuxième règles à la même liste initiale de mots, et ainsi de suite. Et lorsque la dernière règle est appliquée alors on ajoute dans la liste initiale tous les mots créés. Puis on réitère le processus énumératif.
Notez que cet exemple est un exemple particulier qui correspond à une grammaire algébrique. Ces grammaires sont très utilisées en informatique car elle définissent les langages algèbriques, et parceque de nombreux langages informatiques sont des langages algèbriques.
Le langage d'opérateurs d'arité fixe est un langage algébrique. Par exemple, considérons le langage de présentation suivante :
`"<"a,b,f"(.)",g"(.,.)>" = {a,b,f(a),f(b),g(a,a),g(a,b),g(b,a),g(b,b),g(a,f(a)),....,g(f(g(a,a)),f(b)),...}`
Ce langage, appelé aussi domaine de Herbrand, possède la grammaire suivante :
`E->a"|"b"|"f(E)"|"g(E,E)`
Le langage alpha est aussi un langage algébrique.
`{alpha, alpha(alpha), alpha(alpha,alpha),alpha(alpha)(alpha), alpha(alpha,alpha,alpha), alpha(alpha(alpha,alpha)),...}`
Ce langage alpha possède la grammaire suivante :
Le langage alpha étendu aux listes est aussi un langage algébrique.`E->alpha"|"E(S)`
`S->E"|"E","S`
`{alpha, alpha(alpha), (alpha,alpha), alpha(alpha,alpha), alpha(alpha)(alpha), (alpha,alpha,alpha), (alpha, alpha(alpha)), (alpha(alpha),alpha), (alpha,alpha)(alpha), alpha(alpha,alpha,alpha),...}`
Ce langage alpha possède la grammaire suivante :
`E->alpha"|"E(S)"|"(S)`
`S->E"|"E","S`
Pour résumer :
`S->E"|"E","S`Langage alpha étendu aux listes
`S->E"|"E","S`
On donne une définition de la grammaire algèbrique qui s'accorde mieux avec celle de théorie de réécriture algébrique.
Une grammaire algébrique est un ensemble fini de méta-mots et de règles de la forme suivante :
a → M
où a désigne un caractère, et M désigne un méta-mot.
La grammaire algébrique est un énumérateur des mots du langage algèbrique correspondant. L'énumération induit un ordre de complexité des productions. La complexité de production d'un mot ou d'un méta-mot est le nombre minimal de fois qu'il faut appliquer des règles de la grammaire pour le produire.
Cet ordre d'énumération est incomplet car beaucoup de mots ont un même niveau de complexité de production. Cet ordre peut être rendu complet en ordonnant les méta-mots et règles de la grammaire. C'est pourquoi les grammaires sont souvent présentées sous forme de liste plus tôt que d'ensemble, sachant que cette complétion de structure ne fait que déterminer un ordre précis de production et laisse entrevoir ce que pourrait être une heuristique.
Vous aurez remarqué que l'on ne pas préalablement définie qu'elles étaient les caractères et quelles étaits les symboles jouant le rôle de variable. Car dans une grammaire algébrique, il y a un moyen de reconnaitre les symboles des caractères. Ce sont les premiers termes des règles. L'ensemble des caractères utilisés comme premier terme d'une règle est appelé l'ensemble des variables. Et les mot produits qui contiennent au moins un de ces caractères ne sont pas des mots du langage, mais des méta-mots du méta-langage qui peuvent être ajoutés à la théorie comme on ajoute des propriétés.
Par exemple considérons la grammaire suivante décrite par une liste comprenant des méta-mots préfixés par le symbole `"→"`, et des règles composée d'une variable suivi du symbole `"→"` et d'un méta-mot :
`("→"axy,x"→"aybz,y"→"by,"→"y,z"→"yy,y"→"epsilon)`
Cet exemple peut se noter come suit :
`((axy),(x"→"aybz),(y"→"by),(y),(z"→"yy),(y"→"epsilon))`
L'ordre des règles et méta-mots détermine précisement un ordre d'énumération des mots et méta-mots.
L'automate lit un mot, caractère par caractère, les uns à la suite des autres sans revenir en arrière. Il retourne `0` s'il refuse le mot, et `1` s'il l'accepte. Et il peut refuser le mot sans le lire complètement.
L'automate pilote une machine possèdant un ruban et une tête de lecture. Le ruban est composé d'une liste de cases contenant le mot écrit un caractère par case, et où dans les autres case se trouve le méta-caractère blanc. La tête de lecture est positionnée sur la première cases.
A chaque étape, l'automate lit le caractère sous la tête de lecture. S'il y a un caractère autre que le méta-caractère blanc, alors il déplace la tête de lecture d'une case sur la droite et effectue une transition déterminée : Soit il retourne `0` et s'arréte, ou bien il change d'état. Parcontre s'il lit un méta-caractère-blanc, c'est que le mot a été lu, alors il retourne `1` si l'état dans lequel il se trouve est un état acceptant, et il retourne `0` sinon.
L'automate est un graphe où les sommets représentent les états possibles de l'automate, et où les arc représentent les transitions possibles de l'automate et sont étiqueté d'un caractère. Chaque transition correspond à la condition de lire ce caractère particulier sous la tête de lecture. Chaque transition est ainsi étiquetée d'un caractère. Si aucune transition n'est possible l'automate retourne `0` et s'arrête.
L'ensemble des états `E` est finie. L'automate possède un état initiale noté `e_1`, c'est l'état dans lequel se trouve l'automate lorsqu'il démarre. La tête de lecture doit se trouver sur la première case. L'ensemble des états `E` est divisé en deux parties disjointes, les états acceptant `E_1` et les états refusant `E_0`.
`E = E_0 + E_1`
L'automate s'arrète dans deux cas : lorsque le caractère lu est le méta-caractère blanc auquel cas il retourne `1` si l'état en cours est acceptant et `0` sinon, ou si aucune transition n'est possible auquel cas il retourne `0`.
L'automate est déterministe, c'est à dire que l'état initial est parfaitement déterminé et à chaque étape il y a au plus une seul transition possible.
Un automate déterministe possède un état initial `e_1 "∈" E`, une fonction de transition de `(E"×"A)"↦"E`, et un ensemble d'état acceptants. Il est ainsi représenté sous forme d'un triplet.
Le nombre d'automates déterministe distincts comprenant `n` états et opérant sur un alphabet de `k` caractères est donc `n2^n(n"+"1)^(nk)`.
Voici un exemple d'automate déterministe représenté par un état initial, une fonction de `(E"×"A)"↦"E`, et un ensemble d'états acceptant `E_1`. Les états de l'automate sont notés ici pour l'exemple par des chiffres :
`(1, {{:((1,a)"↦"2),( (2,b)"↦"2),( (2,a)"↦"3),( (3,a)"↦"4),( (3,c)"↦"1):}}, {2,3})`
On remarque alors l'existence d'une grammaire algébrique associée qui engendre exactement le langage accepté par l'automate.
`T = {{:(1), (1"→"a2), (2"→"b2|a3|ε), (3"→"a4|c1|ε):}}`
Avec l'alphabet `A = {a,b,c}` et la liste des symboles `S={1,2,3}`, distinction qu'il n'est pas nécessaire de préciser si `T` est réputé être une grammaire algébrique.
Un automate non-déterministe possède un ensemble d''états initiales possibles, une fonction de transition de `(E"×"A"*")"↦"ccP(E)`, et une partition de `E = E_0 + E_1` en états acceptant et états refusant.
Dans un automate non déterministe, à chaque étape, plusieurs possibilités de changement d'état sont possibles ouvrant autant de une nouvelle voie qu'll faut explorer si les autres voies échouent. Le nombre de possibilités potentielles à explorer se démultiplie à chaque étape et s'accroit donc exponentiellement. Il existe un moyen de résoudre cette difficultée et de revenir à une complexité linéaire. Cela consiste à rendre l'automate déterministe, c'est à dire qu'à chaque lecture d'un caractère l'automate n'ait au plus qu'un seul choix de changement d'état possible.
Une grammaire est rationnelle droite si toutes ses règles ont une des deux formes :
`X"→"alphaY`
`X"→"alpha`
où `X"∈"S`, `Y"∈"S`, `alpha"∈"A"*"`, sachant que les symboles de `S` sont exactement les premier termes des règles de la grammaires considérée.
Toute grammaire rationnelle possède un automate non-déterministe qui reconnait le langage qu'elle énumére. Cet automate s'obtient comme suit :
Considéons par exemple la grammaire suivante :
`aY`
`XaX`
`X"→" bY"|"aZ`
`Y"→" c\c"|"aX"|"ε`
`Z"→" bZ"|"X`
On construit l'automate noyaux à l'aide des seuls règles de la grammaire :
`(X,b)"↦"Y`
`(X,a)"↦"Z`
`(Y,c\c)"↦Fin"`
`(Y,a)"↦"X`
`Y " est un état acceptant"`
`(Z,b)"↦"Z`
`(Z,ε)"↦"Z`
On nomme `hatX, hatY, hatZ` des copies de cet automate noyaux avec comme état initial respectif `X,Y,Z`. Puis on construit une composition parallèle et série d'automates pour comprendre les méta-mots de la grammaire `aY` et `XaX`.
Réciproquement, tout automate non-déterministe possède une grammaire rationnelle qui énumère le langage qu'il reconnait. Cet grammaire s'obtient comme suit :
Considéons par exemple l'automate suivant :
`({X,Z}, {{:((X,bac)"↦"Y),( (Y,b)"↦"Y),( (Y,ba)"↦"Z),( (Z,a)"↦"Z),( (Z,ca)"↦"X):}}, {Y,Z})`
On construit la grammaire à l'aide des états initiaux, des arcs, et des états acceptants de l'automate :
`X"↦"bacY`
`Y"↦"bY`
`Y"↦"baZ`
`Z"↦"aZ`
`Z"↦"caX`
`Y"↦"epsilon`
`Z"↦"epsilon`
Chaque automate engendre une grammaire rationnelle et réciproquement chaque grammaire rationnelle engendre un automate, tout deux déterminant le même langage rationnelle. Une grammaire rationnelle peut être compilée en une grammaire dont l'automate est déterministe, comme suit :
Reprenons un exemple de grammaire :
`B`
`C`
`B → abB"|"aC`
`C → cB"|"cC"|"baB"|"ε`
Les symboles de la grammaire, c'est à dire les caractères qui sont au moins une fois premier membre d'une règle, correspondront à des états de l'automate déterministe.
A chaque étape, l'automate se trouve dans un état `B` ou `C`, puis lit le caractère suivant. Il peut alors emprunter l'arrète partant de l'état en cours et qui porte le caractère en label.
On scinde les arrètes ayant un label de plusieurs lettres consécutives en créant autant de nouveaux états intermédiaires désignés par des lettres supplémentaires (symboles) :
`B`
`C`
`B → aD"|"aC`
`C → cB"|"cC"|"bE"|"ε`
`D → bB`
`E → aB`
Lorsqu'il y a plusieurs méta-mots simples tels que `B` et `C` alors il existe plusieurs états initials possibles. On crée un nouvel état que l'on nomme par la réunion des états initiaux. Et ce nouvel état va remplacer dans la grammaire les états initiaux. Le comportement de ce nouvel état cummule les possibilités de changement d'état de chacun de ses états membres :
`{B,C}`
`B → aD"|"aC`
`C → cB"|"cC"|"bE"|"ε`
`D → bB`
`E → aB`
`{B,C} → aD"|"aC"|"cB"|"cC"|"bE"|"ε`
Pour chaque état, lorsqu'il existe plusieurs choix possibles de changement d'état, on crée un nouvel état que l'on nomme par la réunion des états atteignables. Le comportement de ce nouvel état cummule les possibilités de changement d'état de chacun de ses états membres. Ayant modifié la définition de l'état `B` et de l'état `C`, on peut recalculer l'état `{B,C}` toujours comme cummulant les prossibilités de `B` et de `C`:
`{B,C}`
`B → a{C,D}`
`C → c{B,C}"|"bE"|"ε`
`D → bB`
`E → aB`
`{C,D} → c{B,C}"|"bE"|"ε"|"bB`
`{B,C} → a{C,D}"|"c{B,C}"|"bE"|"ε`
Puis on répète cette opération sur les 2 nouveaux états créés `{C,D}` et `{B,C}` :
`{B,C}`
`B → a{C,D}`
`C → c{B,C}"|"bE"|"ε`
`D → bB`
`E → aB`
`{C,D} → c{B,C}"|"b{B,E}"|"ε`
`{B,C} → a{C,D}"|"c{B,C}"|"bE"|"ε`
`{B,E} → a{C,D}"|"aB`
Puis on répète cette opération sur le nouvel état créé `{B,E}` :
`{B,C}`
`B → a{C,D}`
`C → c{B,C}"|"bE"|"ε`
`D → bB`
`E → aB`
`{C,D} → c{B,C}"|"b{B,E}"|"ε`
`{B,C} → a{C,D}"|"c{B,C}"|"bE"|"ε`
`{B,E} → a{B,C,D}`
`{B,C,D} → a{C,D}"|"c{B,C}"|"bE"|"ε"|"bB`
Puis on répète cette opération sur le nouvel état créé `{B,C,D}` :
`{B,C}`
`B → a{C,D}`
`C → c{B,C}"|"bE"|"ε`
`D → bB`
`E → aB`
`{C,D} → c{B,C}"|"b{B,E}"|"ε`
`{B,C} → a{C,D}"|"c{B,C}"|"bE"|"ε`
`{B,E} → a{B,C,D}`
`{B,C,D} → a{C,D}"|"c{B,C}"|"b{B,E}"|"ε`
On obtient ainsi un automate déterministe :
`{B,C}`
`B → a{C,D}`
`C → c{B,C}"|"bE"|"ε`
`D → bB`
`E → aB`
`{C,D} → c{B,C}"|"b{B,E}"|"ε`
`{B,C} → a{C,D}"|"c{B,C}"|"bE"|"ε`
`{B,E} → a{B,C,D}`
`{B,C,D} → a{C,D}"|"c{B,C}"|"b{B,E}"|"ε`
L'état initial est `{B,C}`
La reconnaissance d'un mot d'un langage rationnel est donc de complexité linéaire. A chaque étape, l'automate lit le caractère suivant dans le mot, et il y a au plus qu'une seul possibilité de changement d'état. Si il n'y a pas de possibilié l'automate s'arrête en retournant 0, sinon il applique l'unique possibilité, effectue le changement d'état et lit le caractère suivant. Lorsqu'il n'y a plus de caractère à lire, selon qu'il se trouve sur un état acceptant ou non, il s'arrête et retourne respectivement 1 ou 0.
Cette compilation de la grammaire permet de rendre tout automate non-déterministe en un automate déterministe.
Si nous avions dans notre grammaire des méta-mots plus complexes tel que par exemple `aBaC` et `BBa` au lieu de simplement `B` et `C`, on commencerait par les remplacer comme suit, en créant autant de nouveaux états intermédiaires désignés par des lettres supplémentaires (symboles) `X_1,X_2,X_3,X_4` et `Y_1,Y_2,Y_3` :
`X_1`
`X_1→aX_2`
`X_2→BX_3`
`X_3→aX_4`
`X_4→C`
`Y_1`
`Y_1→BY_2`
`Y_2→BY_3`
`Y_3→a`
La hiérarchie de Chomsky est une classification des langages formels, découverte par Noam Chomsky en 1956. Noam Chomsky est linguiste et philosophe américain, né en 1928 à Philadelphie en Pennsylvanie.
On classifie 4 types de grammaire qui correspondent à 4 types de langage formelle, et qui correspondent à 4 types d'automate. La grammaire énumère les mots de son langage tandis que l'automate accepte les mots de son langage.
Chaque type de grammaire correspond à des restrictions posées sur la formes des règles utilisées. Chaque type d'automate correspond à un type de machine programmable.
On note par `alpha, beta, gamma,...` les variables désignant un mot terminale c'est à dire appartenant à `A"*"`. On note par `Gamma, Theta, Phi, Psi,...` les variables désignant un mot terminal ou non c'est à dire appartenant à `(A+S)"*"`. On note par `x,y,z,...` les variables désignant un caractère terminal c'est à dire appartenant à `A`. On note par `X,Y,Z,...` les variables désignant les symboles (les caractères non terminaux) c'est à dire appartenant à `S`.
Type 0 : Grammaire générale
Pas de restriction sur les règles.
Machine de TuringType 1 : Grammaire sensible au contexte
Les règles sont de la forme suivante :`Gamma→Theta`
où `Gamma"∈"(A"+"S)"*"` et `Theta"∈"(A"+"S)"*"` mais dont les longueurs doivent véfier :
`|Gamma| ≤ |Theta|`
Automate à ruban à borne linéaire
La complexité en ressource de ruban est linéaire. C'est à dire qu'il existe deux nombres `a` et `b` tel que pour tout mots d'entré `w` occupant `|w|` cases sur le ruban, la taille de rubans utilisé lors du calcul, l'excursion maximum de la tête de lecture de la machine de Turing, ne dépasse pas `a|w| + b` cases.Type 2 : Grammaire algébrique
Les règles sont de la forme suivante :`X→ alpha`
où `X"∈"S`, `alpha"∈"A"*"`
Langage algèbrique : Langage dit hors contexte : la substitution d'une portion de mot ne dépend pas de ce qu'il y a autours mais uniquement de ce que contient la portion.
Automate à pile
Automate possédant une pile non bornée.
Type 3 : Grammaire rationnelle
La grammaire rationnelle droite : Les règles sont de la forme suivante :`X"→"alphaY`
`X"→"alpha`La grammaire rationnelle gauche : Les règles sont de la forme suivante :
`X"→"Yalpha`
`X"→"alpha`où `X"∈"S`, `Y"∈"S`, `alpha"∈"A"*"`
Langage rationnel : construit à partire des caractères en utilisant les 3 opérations que sont l'union, la concatenation, et la fermeture de Kleene.
Si nous désignons par type n, l'ensembles des langages engendrés par des grammaires de type n, alors nous pouvons écrire la suite d'inclusions strictes suivantes :
type 3 < type 2 < type 1 < type 0
On définie les langages suivants : Les langages singleton ne contenant qu'un mot égale à un caractère et le langage singleton contenant le mot vide {a}, {b}, {c}, {ε}. Par abus de notation on les note aussi par a, b, c, ε.
On définie dans l'ensemble des langages les opérateurs suivants :
L'ensemble des langages réguliers R d'alphabet {a,b,c} est engendré par {Ø, a, b, c, ε, (x,y)→x|y, (x,y)→xy, x→x*}
R = < Ø, a, b, c, ε (x,y)→x|y, (x,y)→xy, x→x* >
On attribue habituellement une priorité syntaxique de la plus élevé à la plus basse suivantes : cloture de Kleene, concatenation, union.