Langage de caractères
et hiérarchie de Chomsky

 

    1. Introduction
      1. Monoïde défini par l'opération de concaténation
      2. Monoïde défini par des fonctions unaires
    2. Codage des mots
    3. Production
    4. Règles de réécriture
      1. Les règles de réécritures sont des propositions
      2. Notation étendue aux ensembles
      3. Composition et application des propositions entre-elles
      4. Notation doublement étendue aux ensembles
      5. Notation doublement étendue aux arrangements, aux listes et aux sacs
    5. Les théories sont des grammaires
    6. Extension élémentaire
    7. Grammaire
    8. Enumérabilité
    9. Hiérarchie de Chomsky
    10. Automate
    11. Compilation des grammaires régulières
    12. Programmation des automates finis déterministes
    13. La construction des langages réguliers

     

1) Introduction

Les langues écrites utilisent un alphabet fini et leurs mots sont des séquences de caractères appartenants à cet alphabet. C'est ainsi que l'on définie les langages de caractères, dits langages formels. Etant donné un alphabet `ccA = {a,b,c}`. Le langage mère d'alphabet `ccA` se note `ccA"*"`. 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é `ε`.

`ccA = {a, b, c}`
`ccA"*" = {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab,...}`

Les mots du langage mère sont les séquences finies de caractères appartenant à l'alphabet, et il existe un mot particulier, noté `ε`, qu'est la séquence vide de caractère. Et on ne fait pas de distinction entre un caractère et la séquence singleton le contenant. De telle sorte que `ccA"⊂"ccA"*"` et que `ccA"*"` constitue la clôture de `ccA` par concaténation et par ajout du mot vide `ε`. Le symbole `"*"` est l'opérateur de Kleene qui procède à cette clôture.

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 structure : soit de façon classique en utilisant l'opérateur binaire de concaténation, soit en utilisant seulement des opérateurs unaires :

1.1) Monoïde défini par l'opération de concaténation

La structure de `ccA"*"` comprend des opérateurs zéro-aire que sont les caractères de l'alphabet, un opérateur zéro-aire particulier qu'est `ε`, et un opérateur binaire qu'est la concaténation et que l'on note `"⋆"`. Pourtant le symbole `"⋆"` n'apparait pas dans les expressions des mots. En effet c'est une opération abstraite qui apparait dans notre façon de voir selon un paradigme constructif. 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 :

`ccA"*" = {ε, 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 structure se présente en notation programmative et linguistique comme suit (voir Structures fondamentales) :

`ccA"*" = `Monoïde trigène `("⋆", ε, a,b,c)`

`ccA"*" = "<"ε, 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}`

L'ensemble `ccA` est l'alphabet fini qui engendre le monoïde `ccA"*"`. 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 `ccA` est le monoïde libre engendré par `ccA` et se note `ccA"*"`.

Si on enlève l'élément ε, on obtient une structure plus simple notée `ccA^+ = ccA"*""-"{ε}` se présentant en notation linguistique et programmative comme suit :

`ccA^+ = "<"a, b, c, "⋆>" "/" {"⋆"` est associatif`}`
`ccA^+ = `Semi-groupe trigène `("⋆",a,b,c)`

Mais d'un point de vue catégoriel, il s'agit potentiellement de la même structure, l'élément neutre `ε` pouvant être ajouté sans modifier la théorie antérieur restreinte à l'ensemble sous-jacent initiale, c'est à dire sans changer les propriétés des autres opérateurs restreintes à l'ensemble sous-jacent tel qu'il était avant l'ajout de l'élément `ε`.

Autre notation où `ccA` est un ensemble fini :

`ccA"*" = `Monoïde de type fini `("⋆", ε, ccA)`

`ccA"*" = "<"ε, "@"ccA, "⋆>" "/" {"⋆"` est associatif, `ε` est l'élément neutre de `"⋆"}`

`"@"ccA` doit être remplacé par la séquence des éléments de `ccA`.

Enfin, 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 désignera le monoïde suivant :

`"<"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 `ε`.

1.2) Monoïde défini par des fonctions unaires

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 fonctions 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 fonctions unaires engendrées à partir des trois fonctions 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 fonctions 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 fonctions 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 fonctions engendrées par ce procédé soient réellement distinctes en tant que fonction sur cet ensemble.

2) Codage des mots

Prenons quelques caractères : `a, b, c`, et regroupons-les dans un ensemble `ccA={a,b,c}` appelé alphabet. Le langage mère noté `ccA"*"` en est la clôture par concaténation et par ajout du mot vide. :

`ccA"*" = {ε, 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 `ccA` 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 `ccA`. Un langage `ccL` d'alphabet `ccA` est un sous ensemble du langage mère `ccA"*"`. La seul contrainte que nous nous fixons sur l'alphabet `ccA` est qu'il soit fini, et sur le langage `ccL` est qu'il soit énumérable.

On code les `n` caractères de l'alphabet `ccA` par les entiers de `1` à `n`. Puis on code les mots de `ccA"*"` par un développement en base `n` comme suit :

Le mot vide `ε` a un code égale à zéro. Le mot d'un seul caractère a un code égale à celui du caractère. Si l'alphabet est composé de 3 cararctères `a,b,c`, codés comme suivant : `a"="1`, `b"="2`, `c"="3`, le code d'un mot correspond alors à un développement en base 3. Par exemples :

Le mot `abc` possède comme code `1 + 2"∗"3 + 3"∗"3^2 = 34`
Le mot `aaaa` possède comme code `1"∗"3^0 + 1"∗"3^1+ 1"∗"3^2 + 1"∗"3^3 = 40`

Ce codage respecte l'ordre des mots selon leur taille.

Ce codage est une bijection entre `ccA"*"` et `NN`. Autrement dit, il est totalement dense, il constitue un algorithme de compression totale, on ne peut pas comprimer davantage l'information.

3) Production

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 choisie comme symbole de production, le symbole de démonstration `"⊢"`. Et c'est pourquoi un ensemble finis de règles constituera une théorie.

Nous allons d'abord nous restreindre à des règles de productions plus simples ne transformant qu'un mot à la fois et ne produisant qu'un nombre fini de mots à la fois.

4) Règles de réécriture

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 à `ccA"*"` que l'on note séparés par le symbôle `"→"`. Autrement dit, l'ensemble des règles est :

`ccA"*"^2`

La règle appliquée à un mot, produit un nombre 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 en notation anglaise ou en notation française comme suit :

`(ab"→"ba)(abab) = {baab, ab\ba}`        `(abab)^ab"→"ba = {baab, ab\ba}`

4.1) Les règles de réécritures sont des propositions

La règle de réécriture semble appliquer une règle d'égalité entre deux portions de mot, en les substituant que dans un sens donné. Un lien étroit s'opère entre la grammaire qui regroupe l'ensemble des règles de réécriture choisies, et la présentation de la structure de 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 :

Présentation de monoïde
Grammaire
`"<"a,b,c">" "/" {ab"="ba, abc"="c, c\c"="1}`
`ab"→"ba`
`ba"→"ab`
`abc"→"c`
`c"→"abc`
`ε"→"c\c`
`c\c"→"ε`

Un monoïde est présenté habituellement en notation multiplicative, et le `1` désigne l'élément neutre c'est à dire ici le mot vide `ε`.

La règle de réécriture correspond à une demi-règle d'égalité muni d'un sens. Toutes deux font partie du langage des propriétés. Les règles de réécritures enrichissent le langage des propriétés des monoïdes. Par exemple, nous avons :

`{ab"→"ba, ba"→"ab} <=> {ab"="ba}`

Dans notre étude des langages formels, le langage des propriétés ne contient pour l'instant que les règles de réecriture. Mais le langage des propriétés doit être une extension du langage des données, donc il doit contenir les mots. Un mot doit pouvoir être considéré comme une proposition (ou propriété) et donc doit être considéré en quelque sorte comme une règle. Il traduit en terme programmatif la production de ce mot à partir uniquement de lui-même en tant que règle. Ces mots sont aussi appellés mots générateurs du langage de caractères. Ainsi, le langage des propriétés s'étend et comprend les mots et les règles :

`ccA"*" + ccA"*"^2`

Un élément qui peut être un mot ou une règle, s'appellera une proposition ou une propriété. Ainsi le langage des propositions, aussi appelé langage des propriétés, contient à la fois le langage des mots, aussi appelé langage de caractères, et le langage des règles de réécriture.

Considérons par exemple la théorie `ccT={abc, ab"→"ba}` composé d'un mot et d'une règle. Cette théorie démontre le mot `bac` ce que nous écrivons par :

`ccT⊢bac`

La démonstration se fait en appliquant des règles (en notation anglaise et française) :

`(ab"→"ba)(abc)=bac` `abc^(ab"→"ba)=bac`

Puisqu'une règle est une proposition, elle peut faire l'objet d'une démonstration à partir d'une théorie `ccT`. Considérons par exemple la théorie `ccT={ab"→"bac, ba"→"c}` composé de deux règles. Cette théorie démontre la règle `ab"→"c\c` ce que nous écrivons par :

`ccT⊢ab"→"c\c`

La démonstration se fait en appliquant des règles (en notation anglaise et française) :

`(ba"→"c)(ab"→"bac) = ab"→"c\c` `(ab"→"bac)^(ba"→"c) = ab"→"c\c`

Notez que lorqu'une règle s'applique à une autre règle, elle ne s'applique qu'au second membre de la règle en question, et que les seules règles de déduction utilisées pour ces démonstrations sont l'application d'une règle à un mot et l'application d'une règle à une règle.

4.2) Notation étendue aux ensembles

Par soucis de symétrie, on adopte la notation étendue aux ensembles. Une règle appliquée à un ensemble de propositions, retourne la réunion des ensembles résultats. Etant donné une règle `r`, des propositions `x,y,z` et un ensemble de propositions `ccE`, nous avons :

`r{x} = r(x)` `{x}^r = x^r`
`r({x,y}) = r{x,y}` `({x,y})^r = {x,y}^r`
`r{x,y,z} = r(x) uu r(y) uu r(z)` `{x,y,z}^r = x^r uu y^r uu z^r`
`r(ccE) = uuu_(x in ccE) r(x)` `ccE^r = uuu_(x in ccE) x^r`
`r^2(ccE) = (r"∘"r)(ccE) = r(r(ccE))`

`ccE^(r^2) = ccE^(rr) = (ccE^r)^r`

Considérons par exemple la règle `r` définie par `ab"→"ba`. Cette règle remplace dans chaque mot, et dans le second membre de chaque règle, un sous-mot `ab` par le sous-mot `ba`, mais ne procède qu'à une et une seul substitution à la fois. Par exemples :

`r{}={}` `{}^r={}`
`r{a}={}` `{a}^r={}`
`r{ba} ={}` `{ba}^r ={}`
`r{ab} = {ba}` `{ab}^r = {ba}`
`r{a, b, ab}={ba}` `{a, b, ab}^r={ba}`
`r{ab, a"→"ab}={ba, a"→"ba}` `{ab, a"→"ab}^r={ba, a"→"ba}`
`r^2{ab} = (r"∘"r){ab} = r(r{ab}) = r{ba} = {}` `{ab}^(r^2) ={ab}^(rr) = ({ab}^r)^r = {ba}^r = {}`
   
`r{abaab}  =   {baaab, ababa}` `{abaab}^r  =   {baaab, ababa}`
`r^2{abaab}  =   {baaba, ab\baa}` `{abaab}^(r^2)  =   {baaba, ab\baa}`
`r^3{abaab}  =   {babaa}` `{abaab}^(r^3)  =   {babaa}`
`r^4{abaab}  =   {b\baaa}` `{abaab}^(r^4)  =   {b\baaa}`
`r^5{abaab}  =   {}` `{abaab}^(r^5)  =   {}`
   
`r{ab, a"→"ab}  =   {ba, a"→"ba}` `{ab, a"→"ab}^r  =   {ba, a"→"ba}`
`r^2{ab, a"→"ab}  =   {}` `{ab, a"→"ab}^(r^2)  =   {}`
   

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 d'un mot, ou du second membre d'une règle. Exemple :

`(ε"→"ab){abc} = {ababc, aab\bc, ababc, abcab}`
`abc^(ε"→"ab) = {ababc, aab\bc, ababc, abcab}`

Les règles de réécriture de la forme `x"→"x``x` est un mot quelconque, joue le rôle de filtre, elles retournent tous les mots contenant `x` comme sous-mot et toutes les règles contenant `x` comme sous-mot de leur second membre. Ainsi par exemple :

`(ab"→"ab){a,b\b,aba,bacba, bab,b\ba, a"→"ab, b"→"ba} = {aba,bab, a"→"ab}`
`{a,b\b,aba,bacba, bab,b\ba, a"→"ab, b"→"ba}^(ab"→"ab) = {aba,bab, a"→"ab}`

4.3) Composition et application des propositions entre-elles

Une règle `r_1` peut s'appliquer à une proposition `r_2` pour produire une autre proposition, ou bien se composer à une règle `r_2` pour produire une règle composée, et qui se situe en dehors du langage de propriété.

Notation anglaise
Notation française
Application
`r_2(r_1)`
`r_1^(r_2)`
Composition
`r_2@r_1`
`r_1r_2`

Par exemple la composition `(b"→"d)@(a"→"c)` ne se réduit pas en une proposition du langage des propriétés. Mais quelque soit une troisième proposition `x`, nous avons l'inclusion suivante :

`r_1 = (a"→"c)`  
`r_2 = (b"→"d)`  
   
`r_2(r_1)(x) sube (r_2@r_1)(x) = r_2(r_1(x))` `x^(r_1^(r_2)) sube x^(r_1r_2) = (x^(r_1))^(r_2)`

Autrement dit la règle composée `r_2@r_1` est une règle plus riche qui produit davantage que la règle `r_2(r_1)`. Et en notation française, la règle composée`r_1r_2` est une règle plus riche qui produit davantage que la règle `r_1^(r_2)`.

Etant donné une règle `r`, nous avons :

`r^3 = r@r@r` `r^3 = rrr`
   
`r(r)(r)(x) sube (r@r)(r)(x) sube r^3(x)` `x^(r^(r^r)) sube x^(r^(rr)) sube x^(r^3)`
`r(r)(r)(x) sube (r(r)@r)(x) sube r^3(x)` `x^(r^(r^r)) sube x^(r^rr) sube x^(r^3) `
`r(r(r))(x) = (r@r)(r)(x) sube r^3(x)` `x^((r^r)^r)= x^(r^(rr)) sube x^(r^3)`
`r(r)(r(x)) = (r(r)@r)(x) sube r^3(x)` `(x^r)^(r^r)= x^(r^rr) sube x^(r^3)`
`r(r(r(x))) = (r@r@r)(x) = r^3(x)` `((x^r)^r)^r = x^(rrr)= x^(r^3)`

Etant donné des règles pouvant être composées `r` et `s`, on note `r<=s` si et seulement si quelque soit une proposition `x` nous avons `r(x) sube s(x)`. La règle composée `s` est dite plus riche que la règle composée `r`. Cela permet d'écrire les propriétés précédentes plus simplement :

`r^3 = r@r@r` `r^3 = rrr`
   
`r(r)(r) <= (r@r)(r) <= r^3` `r^(r^r) <= r^(rr) <= x^(r^3)`
`r(r)(r) <= (r(r)@r) <= r^3` `r^(r^r) <= x^(r^rr) <= x^(r^3) `
`(r@r)(r) <= r^3` `(r^r)^r= r^(rr) <= r^3`
`(r(r)@r) <= r^3` `(r^rr) <= x^(r^3)`
`(r@r@r)= r^3` `(rrr)= x^(r^3)`

4.4) Notation doublement étendue aux ensembles

Puis toujours par soucis de symétrie, on étend la notation à la proposition appliquante que l'on remplace par un ensemble de propositions appliquantes.

Etant donné des théories, c'est à dire des ensembles de propositions, c'est à dire des ensembles de règles et de mots, `ccU, ccT`. On définie l'application et la composition comme suit : L'application de `ccT` sur `ccU` va appliquer toutes les règles de `ccT` sur les propositions de `ccU` et va ajouter les mots de `ccT`. Tandis que la composition de `ccT` par `ccU` fait se succéder les deux transformations telles quelles.

Notation anglaise
Notation française
Application
`ccT(ccU)`
`ccU^ccT`
Composition
`ccT@ccU`
`ccUccT`

Lorsque plusieurs règles ont le même premier membre, on les réunie en une seule règle produisant autant de mots étendus 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}`

`(aB"→"C|aa|Ba)(aaB)= {aC, aaa, aBa}` `caB^((aB"→"C|aa|Ba)) = {aC, aaa, aBa}`

4.5) Notation doublemnent étendue aux arrangements, aux listes et aux sacs

En munissant les ensembles d'ordre totale, on obtient des arrangements qui se composent ou s'appliquent entre eux pour produirent d'autres arrangements selon une distribution par défaut vers la droite, et de même pour les listes :

`(:r_1, r_2:)(:s_1,s_2:) = r_1(s_1)uur_1(s_2)uur_2(s_1)uur_2(s_2)`
`(:r_1,r_2:)"∘"(:s_1,s_2:) = r_1"∘"s_1uur_1"∘"s_2uur_2"∘"s_1uur_2"∘"s_2`

`(:s_1,s_2:)^(:r_1, r_2:) = s_1^(r_1) uus_2^(r_1)uus_1^(r_2)uus_2^(r_2)`
`(:s_1,s_2:)(:r_1,r_2:) = s_1r_1uus_2r_1uus_1r_2uus_2r_2`

On définie ainsi les compositions et les applications des listes de propositions, des arrangements de propositions, des sacs de propositions, et des ensembles de propositions.

5) Les théories sont des grammaires

Etant donné une théorie `ccT`, c'est à dire un ensemble de mots et de règles, c'est à dire une grammaire.

`ccT sube (ccA"*" + ccA"*"^2)`

On note `"<"ccT">"`, la clôture démonstrative de `ccT`. C'est l'ensemble de toutes les propositions démontrables par `ccT`. Nous avons :

`"<"ccT">" = {r in (ccA"*" + ccA"*"^2) " / " ccT|--r}`

`"<"ccT">" = ccTuuccT^ccTuuccT^(ccT^2)uuccT^(ccT^3)uu...`

L'ensemnle des propostitions d'arité un, c'est à dire les règles, démontrables par `ccT` se note :

`"<"ccT">"_1`

L'ensemble des propostitions d'arité zéro, c'est à dire les mots, démontrables par `ccT`se note :

`"<"ccT">"_0`

C'est le langage engendré par la grammaire `ccT`.

6) Extension élémentaire

Pour augmenter le pouvoir d'expression de définition des grammaires, on va utiliser des variables, mais sans les quantifier pour l'instant.

Il n'y a pas de différence entre une variable qui n'est pas quantifiée et un nouvel élément que l'on rajoute, sachant qu'il peut être égal à tout élément déjà présent ou constituer vraiment un nouvel élément.

On procéde ainsi à une extension élémentaire de la structure de monoïde. On ajoute à l'alphabet `ccA` des symboles supplémentaires notés en majuscule `A,B,C,...`. L'ensemble des symboles se note `ccS={A,B,C,...}`. Ces symbôles ne sont pas des variables mais des caractères rajoutés à l'alphabet. C'est une extension élémentaire de la structure de monoïde libre, passant de `ccA"*"` à `(ccA+ccS)"*"`.

Etant donné une théorie `ccT`, c'est à dire un ensemble de mots et de règles.

`ccT sube ((ccA + ccS)"*" + (ccA + ccS)"*"^2)`

On note `"<"ccT">"`, la clôture démonstrative de `ccT`. C'est l'ensemble de toutes les propositions démontrables par `ccT`:

`"<"ccT">" = {r in ((ccA + ccS)"*" + (ccA + ccS)"*"^2) " / " ccT|--r}`

`"<"ccT">" = ccTuuccT^ccTuuccT^(ccT^2)uuccT^(ccT^3)uu...`

L'ensemble des propostitions d'arité un, c'est à dire les règles, démontrables par `ccT` se note :

`"<"ccT">"_1`

L'ensemble des propostitions d'arité zéro, c'est à dire les mots, démontrables par `ccT`se note :

`"<"ccT">"_0`

C'est le langage étendu engendré par la grammaire `ccT`. Tandis que le langage défini par la grammaire `ccT` est l'ensemble des mots d'alphabet `ccA` démontrables par `ccT`. Il se note `"<"ccT">" nn ccA"*"` ou bien encore `"<"ccT">"_0 nn ccA"*"`.

7) Grammaire

Une grammaire peut être vue comme un moteur énumérant les mots d'un langage. La grammaire se présente formellement sous forme d'un quadruplet comprenant un alphabet `ccA`, une extension de l'alphabet `ccS`, un ensemble `ccM` de mots initiaux appartenant à `(ccA"+"ccS)"*"`, et un ensemble `ccR` de règles initiales appartenant à `(ccA"+"ccS)"*"^2`. Considérons par exemple la grammaire suivante :

`(ccA,ccS,ccM,ccR) = ({a,b}, {A,B}, {B,aA}, {aA"→"Bb, B"→"aB|Ab|ε})`

L'alphabet est `ccA={a,b}`
L'ensemble des symboles est `ccS={A,B}`
L'ensemble des mots initiaux est `ccM={B,aA}`
L'ensemble des règles initiales est `ccR={aA"→"Bb, B"→"aB|Ab|ε}`

Mais on préfère présenter la grammaire sous la forme d'une théorie, la théorie `ccT = ccM + ccR` , en ayant préalablement prédéfini les alphabets `ccA` et `ccS` ou plus simplement en les reconnaissant selon la casse ; les caractères terminaux sont en minuscules et les symboles ou caractères non terminaux sont en majuscules. La grammaire s'appréhende alors de façon plus simple sous la forme d'une théorie :

`ccT ={B,aA, aA"→"Bb, B"→"aB|Ab|ε}`

La grammaire est un processus de construction de mots, à partir de quelques mots initiaux, ici `B` et `aA`, et de quelques règles initiales, ici aA"→"Bb et B"→"aB|Ab|ε. La grammaire engendre deux langages ; un langage étendu, d'alphabet `ccA"+"ccS` contenant tous les mots étendus, et un langage d'alphabet `ccA` contenant seulement les mots terminaux.

Elle est utilisée pour décrire un langage de programmation. Par exemple la grammaire suivante décrit les expressions arithmétiques :

`ccA = {"+","∗","(",")",0,1,2,3,4,5,6,7,8,9,}`
`ccS = {E,N,C}`

`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.
Le symbole `N` représente un nombre.
Le symbole `C` représente un chiffre.

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é à une liste de mots et règles est celui de la distribution vers la droite.

Les grammaires sont des moteurs énumérant les mots d'un langage, selon un ordre d'énumération respectant la complexité des démonstrations. Reprenons notre exemple sous forme d'arrangement de propositions :

`ccT =(:B,aA, aA"→"Bb, B"→"aB|Ab|ε:)`

Cet arrangement de propositions va produire la suite des arrangements de propositions suivants :

`ccT = (:B,aA, aA"→"Bb, B"→"aB|Ab|ε:)`
`ccT^ccT = (:aB, Ab, ε, Bb, aA"→"aBb|Ab\b|b, B"→"aaB|aAb|a:)`
`ccT^(ccT^2) = (:aaB, aAb, a, aA"→"aaBb|aAb\b|ab, B"→"aaaB|aaAb|aa|Bb\b:)`
`ccT^(ccT^3) = (:aaaB, aaAb, aa, Bb\b, aA"→"aaaBb|aaAb\b|aab|Bb\b\b, B"→"aaaaB|aaaAb|aaa|aBb\b|Ab\b\b|b\b:)`

On voit que le mot `aa` est démontré au niveau `3`. Il faut donc à partir d'un mot initial, appliquer `3` règles initiales pour le produire. On voit que la règle `B"→"aaa` est démontrée au niveau `3`. Il faut donc à partir d'une règle initiale, appliquer 3 règles initiales pour la produire.

On verra plus tard que les grammaires ainsi définies énumèrent tous les langages énumérables.

8) Automate

L'automate lit un mot caractère par caractère les uns à la suite des autres une seul fois et retourne `0` s'il le refuse et `1` s'il l'accepte. Il peut parfois 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 contant chacune un carctère ou le méta-caractère blanc. La tête de lecture est positionnée sur une de ces cases.

A chaque étape, l'automate lit le caractère sous la tête de lecture puis, s'il ne s'arrète pas, déplace la tête de lecture d'une case sur la droite et effectue une transition c'est à dire un changement d'état autorisé.

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. Chaque transition correspond à la condition de lire un caractère particulier sous la tête de lecture définie par la transition. Chaque transition est ainsi étiquetée d'un caractère.

On numérote les états de `1` à `n`. L'état `1` est l'état initial, 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 lettre du mot. L'ensemble des états `ccE = {1,2,3,...,n}` est divisé en deux parties disjointes, les états acceptant `ccE_1` et les états refusant `ccE_0`.

`ccE = ccE_0 + ccE_1`

La valuation d'un états est `0` si c'est un état refusant, et `1` si c'est un état acceptant.

L'automate s'arrète dans deux cas : lorsque le caractère lu est le meta-caractère blanc auquel cas il retourne la valuation de l'état en cours, ou si aucune transition n'est possible auquel cas il retourne `0`.

L'automate est déterministe si à chaque étape il y a au plus une seul transition possible.

Un automate déterministe est une fonction de `(ccE×ccA)->ccE` munie d'une partition de `ccE = ccE_0 + ccE_1`. Le nombre de tels automates distincts comprenant `n` états et opérant sur un alphabet de `k` caractères est donc :

`(n+1)^(nk) + 2^n`

Exemple d'automate déterministe :

`((((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 associée :

`ccT = {1"→"a2, 2"→"b2|a3|ε, 3"→"a4|c1|ε}`

avec `ccA = {a,b,c}` et `ccS={1,2,3}`.

 

 

---- 4 janvier 2018 ----

9) Grammaire régulière et automate non déterministe

On note par `alpha, beta, gamma,...` les variables désignant un mot terminale c'est à dire appartenant à `ccA"*"`. On note par `Gamma, Theta, Phi, Psi,...` les variables désignant un mot terminal ou non c'est à dire appartenant à `(ccA+ccS)"*"`. On note par `x,y,z,...` les variables désignant un caractère terminal c'est à dire appartenant à `ccA`. On note par `X,Y,Z,...` les variables désignant un caractère non terminal c'est à dire appartenant à `ccS`.

Une grammaire est régulière si toutes ses règles ont une des formes :

`X->alphaY`
`X->alpha`

`X "∈" ccS`, `Y "∈" ccS`, `alpha "∈" ccA"*"`

Le processus d'énumération des conclusions vu précédement peut être remplacé par un automate non déterministe comme suit : Chaque règle correspond à une transistion

 

A chaque grammaire régulière correspond canoniquement un automate fini qui accepte le langage engendré par la grammaire. Voici par exemple une grammaire régulière droite utilisant l'alphabet A = {a,b,c} et les caractères non terminaux {B,C}, et son automate correspondant :

Grammaire
Automate
B --> abB | aC
C --> cB | cC | baB | ε

Les états de l'automate sont les caractères non terminaux de la grammaire, B et C. Les états finaux coloriés en gris sont ceux pour lesquels il existe une règle produisant le mot vide.

On suppose un mot initial quelconque tel que aBabCc. La grammaire appliqué à ce mot va engendrer un langage. L'automate générique qui doit reconnaitre ce langage se décompose en plusieurs automates. Il commence par reconnaitre a puis B puis ab puis C puis c. La reconnaissance de B et de C correspond à l'automate de la grammaire en partant de l'état initiale correspondant B ou C. Une difficulté provient du fait que lors d'une étape plusieur changements d'état sont possibles. L'automate est non déterministe. Chaque possibilité d'avancement de l'automate ouvre une nouvelle voie qui doit être analysé, et le nombre de possibilités à explorer se multiplie à chaque fois et devient vite trés grand.

Il existe un moyen de contourner cette difficultée et d'amméliorer considérablement l'efficacité. Cela consiste à rendre l'automate déterministe, c'est à dire qu'à chaque lecture d'un caractère l'automate n'ait qu'un seul choix de changement d'état possible.

11) Programmation des automates finis déterministes

Puisqu'une grammaire régulière déterministe, telle qu'elle est écrite, détermine exactement un algorithme, nous pouvons formaliser un langage de programmation de telle sorte que l'algorithme se transcrive à l'identique de la grammaire.

On reprend notre exemple de grammaire : On code les caractères par 1,2...,n  et on ajoute un caractère, le caractère de fin de mot ε que l'on code par 0. Les états B, C, D, E, {B,C}, {C,D}, {B,E}, {B,C,D} sont codés de 0 à m-1, les codes m et m+1 sont réservés pour arrêter le programme et retourner respectivement false ou true.

Le mot vide et le caractère de fin de mot sont désigner par le même symbole ε, mais ils diffèrent conceptuellement, le mot vide est l'élément neutre de l'opération de concaténation, alors que le caractère de fin de mot relève du protocole de bas niveau. Selon ce protocole que nous mettons en place, le caractère de fin de mot ε apparait obligatoirement après le dernier caractère de chaque mot, ou comme premier caractère du mot vide. le mot vide est utilisé pour désigner les transitions sans lecture de caractère faites par un automate non-déterministe. Le caractère de fin de mot est utilisé pour désigner les transitions faites par un automate déterministe sur l'absence de caractère à lire qui arrête l'automate en retournant "true" ou "false" selon que son état est final ou non.

On considère le sous-programme de base qui consiste à lire séquenciellement le caractère suivant et à retourner son code. En fin de mot il lit le caractère de fin de mot ε de code 0.

Les caractère jouent à la fois un rôle passif, de constituant des mots, et un rôle actif comme composant du programme. On regroupe ainsi le coté objectuel et le coté dynamique dans la même notation. La grammaire est mémorisée dans un tableau G[.,.] à 2 dimensions. Le premier indice varie de 0 à m-1 et correspond aux états possibles B, C, D, E, {B,C}, {C,D}, {B,E}, {B,C,D}, les deux valeurs suivantes F = m et V =m+1 correspondent aux arrêts du programme avec une valeur de retour respectivement false et true. Le second incice varie de 0 à n et correspond aux lettres de l'alphabet, la valeur 0 correspond au caractère fin de mots ε :

G = [B, C, D, E, {B,C}, {C,D}, {B,E}, {B,C,D}]

B = [F,{C,D},F,F]
C = [T,F,E,{B,C}]
D = [F,F,B,F]
E = [F,B,F,F]
{C,D} = [T,F,{B,E},{B,C}]
{B,C} = [T,{C,D},E,{B,C}]
{B,E} = [F,{B,C,D},F,F]
{B,C,D} = [T,{C,D},{B,E},{B,C}]

Ainsi la grammaire est mémorisée dans un tableau de (n+1)*m cases contenant des entiers compris entre 0 et m+1, où n est le nombre de lettres de l'alphabet, et m le nombre d'états de l'automate.

Le programme prends, comme entré, l'état initial X et le mot Y à tester. X et Y sont des variables globales du programme. Le programme consiste à répéter indéfiniment la lecture du caractère suivant, et a effectuer le changement d'état correspondant :

Algorithme
        Répéter indéfiniment
        |     Lire le caractère suivant : c=lit(Y)
        |     changer d'état en conséquence : X=G[X,c]
        |     si X = F retourne false
        |     si X = T retourne true
        Fin

Le mot est mémorisé dans une file Y. L'instruction c=lit(Y) retire le premier caractère de la file Y et le met dans la variable c. Si la file est vide, l'instruction c=lit(Y) met 0 dans c.

L'instruction X=G[X,c] change l'état X de l'auromate selon ; la grammaire G, l'état présent X et le caractère lu c.

 

 

--- 29 décembre 2017 ---

 

Un tel automate peut énumérer les mots qu'il accepte, en procédant à un parcourt

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Calculabilité

Une fonction `f` sur `NN` est dite calculable si et seulement si, il existe un automate à ruban `ccM` qui peut la calculer, c'est à dire si et seulement :

`AAi"∈"NN, i"∈"`Dom`(f)<=> ccM(i)"="f(i)`
`AAi"∈"NN, i"∉"`Dom`(f)<=> ccM(i)"∈"{`FAIL`, oo}`

 

 

Un langage `ccL` est énumérable si et seulement si il est énuméré par une machine de Turing `ccM`. c'est à dire que la machine de Turing appliqué à tous les entiers va produire tous les mots du langages :

`ccL = uuu_(i in NN) {ccM(i)}`

Un langage `ccL` est énumérable si et seulement si il est accepté par une machine de Turing `ccM`, c'est à dire qu'appliqué à un mot du langage, la machine s'arrète au bout d'un temps fini et retourne true, et appliqué à un mot hors du langage, la machine soit retourne false ou bien soit ne s'arrète jamais ce qui correspond à l'infini de Turing `oo`. Voir Les fondements de l'informatique, et l'énumérabilité, La calculabilité des ensembles.

On peut construire une machine K qui accepte le langage L, à partir d'une machine M qui énumère le langage L : La machine K appliqué à un mot m va utiliser la machine M pour produire tous les mots du langage et comparer à chaque fois avec le mot m, et si l'égalité se produit, se terminer en retournant true. De même on peut construire une machine M qui énumère le langage L d'alphabet A à partir d'une machine K qui accepte le langage L : La machine M énumère les mots m du langage libre A* et pour chaque m produit, elle crée un processus de calcul parallèle qui applique la machine K sur ce mot m. Dès qu'un m est accepté, la machine retourne m en continuant en parallèle sa recherche pour les autres mots m.

Si on retir algorithme de calcul parallèle, on obtient une machine qui semi-énumère le langage, c'est à dire que la machine appliquer à tous les entiers va produire tous les mots du langage, mais pour certain entiers le calcul ne s'arrètera jamais et donnera l'infini de Turing. La différence qui existe entre la semi-énumération et l'énumération tient en ce que le calcul en cours de route peut ne pas s'arréter et donner l'infini de Turing. Pour procéder à l'énumération, il faut alors ne pas attendre la réponse et effectuer les calculs suivants en paralèlles, ce qui est procéduralement possible. Donc du point de vue de la calculabilité, la semi-énumérabilité est équivalente à l'énumérabilité.

A chaque grammaire correspond une machine de Turing énumérant son langage, et il existe une machine de Turing acceptant son langage.

Les grammaires comme les programmes sont décrits avec le même langage que celui des données mais enrichie de quelques méta-opérateurs tel que ε, |, -->.... Il existe des types de machines programmabes plus simples que la machine de Turing tel que l'automate fini ainsi que l'automate à pile. La machine de Turing dans sa généralité correspond à l'automate à ruban ou à l'automate à deux piles. Lorsque les grammaires sont plus simples elles engendrent des langages plus simples capables d'être acceptés par des machines programmables plus simples.

 

 

 

Un langage `ccL` est énumérable si et seulement si il est énuméré par une machine de Turing `ccM`. c'est à dire que la machine de Turing appliqué à tous les entiers va produire tous les mots du langages :

`ccL = uuu_(i in NN) {ccM(i)}`

Un langage `ccL` est énumérable si et seulement si il est accepté par une machine de Turing `ccM`, c'est à dire qu'appliqué à un mot du langage, la machine s'arrète au bout d'un temps fini et retourne true, et appliqué à un mot hors du langage, la machine soit retourne false ou bien soit ne s'arrète jamais ce qui correspond à l'infini de Turing `oo`. Voir Les fondements de l'informatique, et l'énumérabilité, La calculabilité des ensembles.

On peut construire une machine K qui accepte le langage L, à partir d'une machine M qui énumère le langage L : La machine K appliqué à un mot m va utiliser la machine M pour produire tous les mots du langage et comparer à chaque fois avec le mot m, et si l'égalité se produit, se terminer en retournant true. De même on peut construire une machine M qui énumère le langage L d'alphabet A à partir d'une machine K qui accepte le langage L : La machine M énumère les mots m du langage libre A* et pour chaque m produit, elle crée un processus de calcul parallèle qui applique la machine K sur ce mot m. Dès qu'un m est accepté, la machine retourne m en continuant en parallèle sa recherche pour les autres mots m.

Si on retir algorithme de calcul parallèle, on obtient une machine qui semi-énumère le langage, c'est à dire que la machine appliquer à tous les entiers va produire tous les mots du langage, mais pour certain entiers le calcul ne s'arrètera jamais et donnera l'infini de Turing. La différence qui existe entre la semi-énumération et l'énumération tient en ce que le calcul en cours de route peut ne pas s'arréter et donner l'infini de Turing. Pour procéder à l'énumération, il faut alors ne pas attendre la réponse et effectuer les calculs suivants en paralèlles, ce qui est procéduralement possible. Donc du point de vue de la calculabilité, la semi-énumérabilité est équivalente à l'énumérabilité.

A chaque grammaire correspond une machine de Turing énumérant son langage, et il existe une machine de Turing acceptant son langage.

Les grammaires comme les programmes sont décrits avec le même langage que celui des données mais enrichie de quelques méta-opérateurs tel que ε, |, -->.... Il existe des types de machines programmabes plus simples que la machine de Turing tel que l'automate fini ainsi que l'automate à pile. La machine de Turing dans sa généralité correspond à l'automate à ruban ou à l'automate à deux piles. Lorsque les grammaires sont plus simples elles engendrent des langages plus simples capables d'être acceptés par des machines programmables plus simples.

8) Hiérarchie de Chomsky

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 langage formelle associé respectivement à 4 types de grammaire et à 4 types d'automates pouvant accepter le langage formel en question.

les grammaires en 4 types selon des restrictions posées sur la formes des règles utilisées, et qui correspondent à 4 types de machines pogrammables pouvant accepter le langage engendré par la grammaire.

Type de grammaire
Type de machine programmable

Type 0 : Grammaire générale
Pas de restriction sur les règles.

Automate à ruban
C'est une machine de Turing

Type 1 : Grammaire sensible au contexte
Les règles sont de la forme suivante :

u --> v

u et v désignent deux mots terminaux ou non,
de longeur |u| ≤ |v|

Automate à ruban à borne linéaire
A borne linéaire signifie que 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 hors-contexte
Les règles sont de la forme suivante :

A --> u

A désigne un caractère non terminal, et u désigne un mot terminal ou non.

Langage hors-contexte : Les caractères terminaux peuvent être substitué par un mot terminal ou non, indépendament des caractères autours. Grace à cela, on peut représenter une dérivation en faisant abstraction de l'ordre d'application des règles de production, à l'aide d'un arbre de dérivation.

Automate à pile
Automate possédant une pile non bornée.

Type 3 : Grammaire régulière
La grammaire régulière droite : Les règles sont de la forme suivante :

A-->wB
A-->w

La grammaire régulière gauche : Les règles sont de la forme suivante :

A-->Bw
A-->w

A et B désignent deux caractères non terminaux, et w désigne un mot terminal.

Langage régulier : construit à partire des langages singletons contenant tous les mots composés d'un seul caractère de l'alphabet et contenant le mot vide, et en utilisant les 3 opérations que sont l'union "|", la concatenation notée par absence de symbole, et la fermeture de Kleene "*".

Automate fini

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

 

10) Compilation des grammaires régulières

La grammaire constitue le programme de l'automate. Une grammaire régulière peut être compilée afin que son automate soit déterministe.

Reprenons notre exemple de grammaire :

B --> abB | aC
C --> cB | cC | baB | ε

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 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 (non terminales) :

B --> aD | aC
C --> cB | cC | bE | ε
D --> bB
E --> aB

Pour chaque règle, 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 :

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 l'opération sur les 2 nouveaux états créés {C,D} et {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 l'opération sur le nouvel état créé {B,E} :

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 l'opération sur le nouvel état créé {B,C,D} :

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 :

Grammaire compilée
Automate déterministe
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} | ε

La reconnaissance d'un mot d'un langage régulier 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 "false", 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 final ou non, il s'arrête et retourne respectivement "true"ou "false".

Cette compilation de la grammaire permet de la rendre déterministe.

L'état initial parmi B, C, D, E, {B,C}, {C,D}, {B,E}, {B,C,D} doit être choisi avant de lancer l'exécution de l'automate.

 

12) La construction des langages réguliers

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 :

  1. L'opérateur binaire union, noté "|", qui consiste à fair la réunion de deux langages.
  2. L'opérateur binaire concaténation noté par absence de symbôle. La concaténation de deux langage est l'ensemble des mots composée d'un mot du premier langage et d'un mot du second langage.
  3. L'opérateur unaire gauche de Kleene, noté "*" , qui consiste à prendre la femeture de Kleene du langage, c'est l'ensemble des mots composés d'un nombre quelconque de mots du langage.

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.

Pierre Wolpert, Introduction à la calculabilité, Dunod, Paris 2006
Site web, université de Brest http://fastnet.univ-brest.fr/~gire/cours

 

Il est possible de généraliser la notion de production à celle d'un processus calculatoire pouvant opérer sur une liste finie ou une énumération infinie de mots et produire une liste finie ou une énumération infinie de mots. Ces processsus se composent entre-eux, comme les processus d'un système UNIX à l'aide de tubes (pipeline), de la même façon que les fonctions se composent entres-elles. La différence tient dans l'arité des entrés et des sorties qui sont variables et peuvent être infinies énumérable, et dans la possibilité du calcul sans fin, un comportement particulier que peut adopter un programme et qui est désigné par l'infini de Turing, ?. Notez que dans le cas général ce comportement est un oracle car pour être certain de ce comportement il faut se placer à la fin des temps.

Le programme ou le processus est beaucoup plus concret que la fonction. La fonction est trop abstraite. Aussi ce n'est pas la fonction qu'il faut définir en premier mais bien le programme ou le processus. La formalisation du programme nécessite de choisire un langage de données pour coder les données, et un langage de programmation pour coder le programme. Le langage de programmation peut être perçu comme une extension du langage de données, il comprend donc le langage de données.

Démontrable veut dire qui peut être construit. C'est pourquoi les intuitionistes ont un point d'avance sur les autres écoles. Et en unifiant de façon pertinente les trois pans du langages que sont le langage de données, le langage de programmation et le langage de propriétés, la construction d'une propriété, autrement dit sa démonstration, signifiera la même chose que la construction d'un programme ou d'une structure.

3.2) Notation étendue aux arrangements

Pour introduire un ordre canonique dans les productions, on adopte la notation étendu aux arrangement. Un arrangement est une liste d'éléments distincts ou bien, un ensemble munie d'un ordre total. Par exemple, la règle `ab"→"ba` appliquée au mot `abab` produira exactement les deux mots `baab` et `ab\ba`., et dans cet ordre par défaut dit de lecture vers la droite, ce qui se note :

`(ab"→"ba)(abab) = (:baab, ab\ba:)`

Et il y a l'ordre symétrique dit de lecture vers la gauche.

Par soucis de symétrie, on adopte la notation étendue aux arrangements. Une règle appliquée à un arrangement de mots retourne la réunion-concaténation des arrangements pour chaque mot. Etant donné une règle `r`, des mots `x,y,z` et un arrangement de mots `ccE`, nous avons :

`r(:x:) = r(x)`
`r((:x,y:)) = r(:x,y:)`
`r(:x,y,z:) = r(x) ⊍ r(y) ⊍ r(z)`
`r(ccE) = ⨃_(x ⋵ ccE) r(x)`
`r^2(ccE) = r(r(ccE))`

Considérons par exemple la règle `r` définie par `ab"→"ba`. Cette règle remplace dans chaque mot, un sous-mot `ab` par le sous-mot `ba`, mais ne procède qu'à une et une seul substitution. Par exemple :

`r(::)=(::)`
`r(:a:)=(::)`
`r(:ba:) =(::)`
`r(:ab:) = (:ba:)`
`r(:a, b, ab:)=(:ba:)`
`r^2(:ab:) = r(r(:ab:)) = r(:ba:) = (::)`
 
`r(:abaab:)  =   (:baaab, ababa:)`
`r^2(:abaab:)  =   (:baaba, ab\baa:)`
`r^3(:abaab:)  =   (:babaa:)`
`r^4(:abaab:)  =   (:b\baaa:)`
`r^5(:abaab:)  =   (::)`

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 d'un mot. Exemple :

`(ε"→"ab)(:abc:) = (:ababc, aab\bc, ababc, abcab:)`

Les règles de réécriture de la forme `x"→"x``x` est un mot quelconque, joue le rôle de filtre, elles retournent tous les mots contenant `x` comme sous-mot. Ainsi par exemple :

`(ab"→"ab)(:a,b\b,aba,bacba, bab,b\ba:) = (:aba,bab:)`

 

 

On introduit un ordre canonique dans les productions en adoptant la notation étendu aux arrangement. Un arrangement est une liste d'éléments distincts ou bien, un ensemble munie d'un ordre total. Par exemple, la règle `ab"→"ba` appliquée au mot `abab` produira exactement les deux mots `baab` et `ab\ba`., et dans cet ordre par défaut dit de lecture vers la droite, ce qui se note :

`(ab"→"ba)(abab) = (:baab, ab\ba:)`

Les arrangements s'assemblent par réunion-concaténation. Par exemple :

`(:x,y,z:) ⊍ (:t,z,u,x:) = (:x,y,z,t,u:)`