mise à jour du 22 juin 2002

ELEMENTS D'INFORMATIQUE THEORIQUE
Ce résumé dérive de l'ouvrage "Mathématiques discrètes"  deKenneth H.Rosen
Remerciements à Jérôme Marchand informaticien de St Jean de Dieu


Grammaire syntagmatique
: G=(V,T,S,P)

V: vocabulaire, ensemble non vide de symboles;
exemple : {phrase, nom propre, le, la, tortue, lièvre, §,…}

un mot dans V est une chaîne de symboles de longueur finie
(dans la suite les mots seront notés par des w indexés
§ identifie la chaine vide
T :termes terminaux, sous ensemble de V qui sont  aboutissements de calculs; exemple : lièvre ,…

S :symbole unique de départ, élément de V; exemple phrase en analyse de langue naturelle

P : Ensemble des productions de la forme w1 --> w2 ( w1 : non terminal) exemple :
phrase --> groupe nominal groupe verbal
phrase --> groupe verbal groupe nominal
groupe nominal --> article nom adjectif

Retour à l'accueil



Dérivations
Soit mot1 = w1w2w3 et mot2= w1w4w3
si w2-->w4 on dira que mot2 est directement dérivable de mot1 et on notera :
mot1==>mot2
si mot1 et mot2 sont dérivés par plusieurs derivations directes successives, on notera
mot1=*>mot2

Langage

Le langage créé par G, noté L(G), est l’ensemble de tous les terminaux qui dérivent de S
Exemple : V=(S,A,a,b), T=(a,b), P=( S-->aA, S-->b, A-->aa)
donne L(G) = (b,aaa) comme langage.

Types de grammaires
type 0 : aucune restriction sur les productions w1-->w2
type 1 : longueur de w2 >= longueur de w1 ou w1--> §
type 2 : w1 est un symbole unique non terminal
type 3 : toutes les productions sont de la forme (w1=A et (w2=aB ou w2=a) avec A et B non terminaux, a terminal) ou w1=S et w2=§


On a : Type 3 contenu dans type 2, contenu dans type 1, contenu dans type 0.
Type 1 : grammaires contextuelles
Type 2 : grammaires algébriques   d’où sont issus les langages algébriques
    (Voir notion d’arbre de dérivation pour une grammaire algébrique)

Type 3 :grammaires régulières qui engendrent les langages régulier liés avec les automates d’états finis.
Retour à l'accueil


Forme de Backus-Naur pour les grammaires type 2
Les grammaires de type 2 n’ont qu’un seul non-terminal du côté gauche.On met tous les non-terminaux entre < et > et on énumère tous les côtés droits des production dans le même énoncé.

Exemple : A-->Aa,A-->a, et A-->AB s’écrit :

<A>::= <A>a | a<A><B>


Autre exemple :

Forme de Backus pour une grammaire produisant des entiers signés :
<entier signé> ::=<signe><entier>
<signe> ::= + | -
<entier> ::=<chiffre>|<chiffre><entier>
<chiffre>::=0 |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9


Exercices Soit la grammaire G suivante :

V={0 , 1 , S}; T={0,1} et P= {S-->0S1, S-->§} produit l’ensemble :
{0n1n pour tout entier n non negatif}
en notant par an une chaine de n symboles a


Machines à états finis avec sortie

C e sont des appareils qui ont :

• un état de départ : S0
un nombre fini d’autres états possibles , par exemple six états notés
S1, S2,…S6
• un nombre fini d’entrées E possibles, par exemple 5 entrées :
des pièces de 5, 10 et 25 cents,
 + un bouton O pour obtenir un jus d’orange JO
 + un bouton R pour un jus de raisin JR.

• une fonction de transition f(E,S) qui défini l' état suivant en fonction  de l’entrée E et de l’état actuel S
• une fonction de sortie g(E,S) qui définit la sortie en fonction des mêmes paramètres


Retour à l'accueil


Une machine à états finis avec sortie: distributeur de boisson

On vérifiera que l'appareil rend bien la monnaie

Etat actuel
Etat suivant = f(E,S)
Sortie = g(E) (-- = rien)
    E-->
5
10
25
O
R
5
10
25
O
R
S0
S1
S2
S5
S0
S0
--
--
--
--
--
S1
S2
S3
S6
S1
S1
--
--
--
--
--
S2
S3
S4
S6
S2
S2
--
--
5
--
--
S3
S4
S5
S6
S3
S3
--
--
10
--
--
S4
S5
S6
S6
S4
S4
--
--
15
--
--
S5
S6
S6
S6
S5
S5
--
5
20
--
--
S6
S6
S6
S6
S6
S6
5
10
25
JO
JR

Les machines de Mealy (1955) sont du type défini ci-dessus. Dans les machines de Moore la fonction g ne dépend que de S.

Dans ces types de machines les entrées et les sorties peuvent toutes deux appartenir au vocabulaire {0,1}.
Dans ce cas la machine fait correspondre toute suite d'entrées binaires à un suite de sorties binaires.

Reconnaissance de langage

En voici un exemple.

La machine suivante reconnait  la suite 111 dès qu'elle est entrée.
Elle donne alors une sortie 1 (équivalente à "Euréka !" ),
sinon elle sort 0.

S0.
             
fontion de transition
Fonction de sortie
Entrée--->

Etat : 

0
1
0
1
S0
S0
S1
0
0
S1
S0
S2
0
0
S2
S0
S2
0
1
Retour à l'accueil


Voici la suite des sorties si les entrées successives sont : 11010111
Entrées
1
1
0
1
0
1
1
1
Etat obtenu
S1
S2
S0
S1
S0
S1
S2
S2
Sortie
0
0
0
0
0
0
0
1
Pour sortir un 1 il faut être en S2 et avoir entré 1; mais pour être en S2 il faut avoir entré prédemment aussi un 1;
mais cette fois précédente ne peut être S2, c'est donc S1 qui ne s'explique que par un 1 à l'ètat S0.
 Dés qu'il arrive un zero la machine passe en
S0.

Fermeture de Kleene
On note par AB la "concaténation" de A avec B, c'est à dire l'ensemble des chaines constituées d'une chaine de A suivie d'une chaine de B. En général AB est différent de BA.
 V* désigne l'ensemble des chaînes issues d'un vocabulaire V. Soit A un sous ensemble de V* On note par A* l'ensemble des chaines constituées par les concaténations d'un nombre arbitraire de chaines de A.
 A* est la fermeture de Kleene de A






AUTOMATES FINIS



La principale utilité des automates finis sera de reconnaitre des langages
.
Ce sont des machines à états finis sans sortie mais comportant un sous ensemble appelé états finaux.

Un automate fini M = (S,I,f,s
0,F) comporte un ensemble fini d'états S, un alphabet d'entrée fini I, un fonction  f(i,s) de l'entrée i et de l'etat actuel s, un état initial s 0 et un ensemble F défini comme étant celui des états finaux
Quand une suite atteint   un état final on dit que la suite est reconnue

Retour à l'accueil




Exemple : Soit l'automate fini S=(S0, S1) F=S0  I=(0,1)  f donné par :

f

0
1
S0
S1
S0
S1
S1
S1
il reconnait toutes les chaines constituées de n≥0 fois 1, seules façons d' obtenir S0, seul état final ;
tout 0 conduit à l'état S1 d'où il n'est plus possible de revenir en S0

Automates fini à comportement non déterminé

La fonction de transition peut définir non un seul mais plusieurs aboutissements possibles.
Ce sont les automates de ce type qui permettent de trouver quel langage est susceptible de reconnaitre un automate fini.
On dit qu'un automate fini non déterministe reconnait une chaine, lorsqu'il existe un état final parmi les états que l'on peut atteindre à partir de cette chaîne
On démontre que, si le langage L est reconnu par l'automate fini non déterministe M0,  il l'est par un automate fini déterministe M1. Ce théorème peut donner lieu à tout un ensemble d'exercices d'informatique théorique : On donne un automate non déterministe ; trouver un automate fini déterministe équivalent !
 
Retour à l'accueil

Reconnaissance de langages

 Il se pose alors le problème de savoir quels sont les langages que peuvent reconnaitre les automates finis .

Stephen Kleene a démontré en 1956 qu'il existe un automate fini susceptible de reconnaitre un langage si et seulement si ce langage dérive d'une grammaire régulière, ou de type 3, telle que définie précédemment. Ces grammaires engendrent des ensembles réguliers au sens de Kleene, qui peuvent être engendrés  à partir de l'ensemble vide, de la chaine vide et d'ensembles à un élément, par concaténation, union et fermeture de Kleene.
Il existe donc des langages qu'aucun automate fini ne peut reconnaitre.

Des modèles computationnels plus puissants permettent d'étendre les possibilités de reconnaissance. Ce sont notamment:

les automates programmables en pile
les automates linéaires bornés
les machines de Turing.

Les automates finis permettent des calculs relativement simples, comme la somme de deux nombres. Ils ne permettent pas, par exemple le calcul du produit de deux nombres. Pour atteindre les possibilités des ordinateurs actuels, il faut recourir à la notion de machine de Turing. Ces dernières  peuvent reconnaître tout langage défini par une grammaire syntagmatique.

Une machine de Turing T=(S,I,f,S0) comporte
• un ensemble fini d'etats internes :S,
• un état de départ S0
• une bande comprenant un nombre infini de cellules où une tête de lecture-écriture peut lire ou écrire les caractères d'un alphabet I
• l' alphabet : I contient,  le symbole vide,
• une fonction  f  de l'état actuel S et du symbole I lu sous la tête de lecture-écriture
• cette fonction f détermine :

- le symbole à écrire en remplacement du symbole lu,
- laquelle des cellules (droite ou gauche) doit ensuite être lue sur la bande (ou passée si elle est vide) , 
- l'état interne suivant

Il a été tenté divers aménagements à la machine de Turing : plusieurs bandes, bandes à deux dimensions,  plusieurs têtes, possibilité de rester immobile, etc. Dans tous les cas on obtient des possibilités identiques à la machine la plus simple.
 De même il a été montré que les diverses définitions qui ont pu être données de la notion d'algorithme de calcul on pu être remplacées par une machine de Turing.

Bien que celà puisse théoriquement se faire il serait irréaliste de vouloir construire des machines de Turing pour effectuer des calculs réels. Par exemple de simples multiplications.


Le Lamda calcul


Une expression de Lamda calcul est definie par la grammaire  très simple suivante :
Expr := ident | constante | lamda ident. Expr | Expr Expr | (Expr)


On montre que le lamda-calcul est en quelque sorte l'équivalent logiciel de la machine de Turing. Il conduit aux mêmes possibilités d'expression.





Retour à l'accueil
.