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 finieT :termes terminaux, sous ensemble de V qui sont aboutissements de calculs; exemple : lièvre ,…
(dans la suite les mots seront notés par des w indexés
§ identifie la chaine vide
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
Soit mot1 = w1w2w3 et mot2= w1w4w3
si w2-->w4 on dira que mot2 est directement dérivable de mot1 et on notera :
mot1==>mot2si 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 STypes de grammaires
Exemple : V=(S,A,a,b), T=(a,b), P=( S-->aA, S-->b, A-->aa)
donne L(G) = (b,aaa) comme langage.
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.
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,• 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
+ un bouton O pour obtenir un jus d’orange JO
+ un bouton R pour un jus de raisin JR.
• une fonction de sortie g(E,S) qui définit la sortie en fonction des mêmes paramètres
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 |
|
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 |
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 |
f
|
||
0
|
1
|
|
S0 |
S1
|
S0
|
S1 |
S1
|
S1
|
les automates programmables en pileLes 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.
les automates linéaires bornés
les machines de Turing.
• un ensemble fini d'etats internes :S,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.
• 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