Embed Size (px)
Citation preview
Machines de Turing
Pr ZEGOUR DJAMEL EDDINE
Ecole Supérieure d’Informatique (ESI)
www.zegour.uuuq.com
email: [email protected]
Machines de Turing : Objectif
On définit deux machines rudimentaires de Turing : machine-caractères et machine-nombres. Ces machines permettant l’initiation à l’algorithmique
Ces machines offrent les opérations suivantes :
CREER_MCAR, LIRECAR, NBRCAR
CREER_MNOMBRE, LIRENOMBRE, NBRNOMBRE
Sémantique des machines de Turing : Il s’agit de les transformer en des formes internes qui permettent de faciliter leur interprétation ou génération de code.
Sémantique des machines de Turing : Quadruplés
Machine-caractères CREER_MCAR(M, [Chaine]), LIRECAR(M,Caractere), NBRCAR(M)
A : pointeur TABOB vers l’objet machine-caractèresB : pointeur dans TABOB vers la constante chaîne de caractères
A : pointeur TABOB vers l’objet machine-caractèresB : pointeur dans TABOB vers l’identificateur
A : pointeur TABOB vers l’objet machine-caractèresC : pointeur dans TABOB vers le résultat
(‘Créer_mcar’, A, B, )
(‘Lirecar’, A, B, )
(‘Nbrcar’, A, ,C )
Sémantique des machines de Turing : Quadruplés
Machine-nombres : CREER_MNOMBRE(M, [Exp1, Exp2, …]), LIRENOMBRE(M,Nombre), NBRNOMBRE(M)
A : pointeur TABOB vers l’objet machine-nombresB : pointeur dans TABCOMP vers la liste des expressionsC : Nombre d’expressions
A : pointeur TABOB vers l’objet machine-nombresB : pointeur dans TABOB vers l’identificateur
A : pointeur TABOB vers l’objet machine-nombresC : pointeur dans TABOB vers le résultat
(‘Créer_mnombre’, A, B, C )
(‘Lirenombre’, A, B, )
(‘Nbrnombre’, A, ,C )
Machines de Turing : Déclarations
Types dans {Entier, Booleen, Car, Chaine}
Sep dans {:, Un, Une, Des}
Cste constante numérique entière
Chaîne chaîne de caractères
Idf identificateur
Opr dans { <, <=, >, >=, =, <> }
Opa dans { +, -, Ou }
Opm dans { *, /, Et }
Sign dans {+, -}
Tableau est synonyme de Vecteur
Init_tableau est synonyme de Init_vecteur
Machines de Turing : Déclarations
<Algo Z> [ ~Soit|Soient~ <Ps> ] Debut <Lis> Fin [;] { ~<Act> | <Fonct>~ [;] }* <Act> Action Idf [ ( <Li> ) ] [;]
[ ~Soit|Soient~ <Ps> ] Debut <Lis> Fin <Fonct> Fonction Idf ( <Li> ) : <Typ>
[ ~Soit|Soient~ <Ps> ] Debut <Lis> Fin <Ps> <S>;{ [~Soit|Soient~] <S>;}* <S> <Li>[Sep ~<Typ>|~Action|Fonction(<Typ>)~ ~]<Li> Idf {, Idf}*
Machines de Turing : Déclarations
<Typ> Types | <Structsimple> | <Structcomplexe> |
Tableau (<Lc>) [De~<Structsimple> | Types~ ] |
<Structsimple> [Structure ](Types {, Types }*)
<Structcomplexe> [Structure ]( ~ Types | Vecteur(Cste) De Types ~ {, ~ Types | Vecteur(Cste) De Types ~ }*)
<Lc> Cste {, Cste}*
Machine_car |
Machine_nombre |
Machines de Turing : Instructions
< Lis > < Inst > { ; < Inst > }* <Inst>
Idf := <Exp> | Lire ( Idf {, Idf }* ) |
Ecrire (<Exp> {,<Exp>}* ) |Tantque <Exp> [ : ] <Lis> Fintantque |Si <Exp> [:] <Lis> [Sinon <Lis>] Fsi |Pour Idf:= <Exp>,<Exp> [, <Exp>][:] <Lis> Finpour |Appel Idf [(Exp {,<Exp>}*)] |
Machines de Turing : Instructions
<Inst>
~ Init_vecteur | Init_struct | ~ ( Idf , [[ ~<Exp>|[[<Exp> {, <Exp>}*]] ~ {, ~<Exp>|[[<Exp> {, <Exp>}*]]~}* ]] ) |
Aff_element ( <Exp> [[ <Exp> {, <Exp> }* ]] ,<Exp> ) |
Aff_struct(Idf, Cste, <Exp>) |
Creer_mnombre
Creer_mcar(Idf, [[ Chaine ]]) |
~Lirecar|Lirenombre~ (Idf, Idf)
Machines de Turing : Expressions
<Exp> <Exps>[ Opr <Exps>]
<Exps> [Sign] <Terme> { Opa <Terme> }*
<Terme> <Facteur>{Opm <Facteur>}*
<Facteur> Idf [(Exp {,<Exp>}*)] | Cste |
( <Exp>) | <Fonct> |
Non <Facteur> | Vrai | Faux | Chaine
<Fonct> Element ( <Fonct> [[ <Exp> {, <Exp> }* ]] ) |
Struct ( Idf, Cste) |
~Nbrcar|NbrNombre~ (Idf)
Sémantique des machines de Turing : Fonctions sémantiques
<Typ> Machine_car | Machine_nombre
Description Fx
<Typ>
Fonctions sémantiques et Descriptions à trouver
Sémantique des machines de Turing : Fonctions sémantiques
<Inst> Creer_mnombre ( Idf , [[ ~<Exp>|[[<Exp> {, <Exp>}*]] ~
{, ~<Exp>|[[<Exp> {, <Exp>}*]]~}* ]] ) |
Description Fx
< Inst>
Fonctions sémantiques et Descriptions à trouver
Sémantique des machines de Turing : Fonctions sémantiques
<Inst> Creer_mcar(Idf, [[ Chaine ]])
Description Fx
< Inst>
Fonctions sémantiques et Descriptions à trouver
Sémantique des machines de Turing : Fonctions sémantiques
<Inst> ~Lirecar|Lirenombre~ (Idf, Idf)
Description Fx
< Inst>
Fonctions sémantiques et Descriptions à trouver
Sémantique des machines de Turing : Fonctions sémantiques
<Fonction> ~Nbrcar|NbrNombre~ (Idf)
Description Fx
< Fonction>
Fonctions sémantiques et Descriptions à trouver
Sémantique des machines-caractères : ExempleSoit mc une machine_car; c un car; compte un entier;debut creer_mcar(mc, ['abc df yhr.'] ); lirecar(mc, c); compte := 0; tq c <> '.' compte := compte + 1; lirecar(mc, c)ftq;ecrire(compte)fin
‘L’ 1 2 0
‘L’ 2 1 1
‘L’ 3 1 2
‘C’ 2 1 0
‘C’ 2 1 1
‘C’ 2 1 2
‘X’ 5 1 3
‘C’ 4 1 3
‘X’ 3 1 4
0
1
2
TABOB5LONGZDD
3
Quadruplés générés
‘Dc’ 1
‘De’ 2
‘Creer’ 0 3
‘Lirec’ 0 1
‘Aff’ 2 4
‘<>’ 1 5 6
‘B’ 6 7 11
‘+E’ 2 7 8
‘Aff’ 2 8
‘Lirec’ 0 1
‘Br’ 5
‘Ecrire’ 0 1
1
2
3
TABTYP MCESB
0
'abc df yhr.‘,’0’,’.’,’1’TABCONS
0 1 2 3
4
5
6
4
5
6
7
8
7
8
TABCOMP 20
910
11
Sémantique des machines-nombres : Exemple
Soit mn une machine_nombre; n un entier; somme un entier;i un entier;debut creer_mnombre(mn, [12,54,67,11,23] ); somme := 0; pour i:=1, nbrnombre(mn) lirenombre(mn, n); somme := somme + n; fpour; ecrire(somme)fin
‘L’ 1 2 0
‘L’ 3 1 1
‘L’ 3 1 2
‘L’ 3 1 3
‘C’ 3 1 0
‘C’ 3 1 1
‘C’ 3 1 2
‘C’ 3 1 3
‘C’ 3 1 4
‘C’ 3 1 5
‘C’ 3 2 6
‘X’ 3 1 4
‘X’ 4 1 5
‘X’ 3 1 6
0
1
2
TABOB
6LONGZDD
3
Quadruplés générés
‘Creer’ 0 0 5
‘Aff’ 2 9
‘:=’ 3 10
‘Nbrno’ 0 11
‘<=’ 3 11 12
‘B’ 12 6 11
‘Lireno’ 0 1
‘+E’ 2 1 13
‘Aff’ 2 13
‘+E’ 3 10 3
‘Br’ 4
‘Ecrire’ 1 1
1
2
3
TABTYP MNEB
0
‘12’,’54’,’67’,’11’,’23’,’0’,’1’
TABCONS 0 1 2 3 4 5 6
4
5
6
4
5
6
7
8
7
8
9
TABCOMP 4,5,6,7,80
21
10
11
12
13
9
10
11
Machines de Turing : Interprétation
Implémentation de la Machine-Caractères (Description PASCAL)
TYPE Typemcar = ^Elementmcar;
Elementmcar = RECORD
Adrchaine : Typechaine ;
Nombre : INTEGER;
Indice_courant : INTEGER
END;
Machines de Turing : Interprétation
Implémentation de la Machine-nombres (Description PASCAL)
TYPE Typemnombre = ^Elementmnombre;
Elementmnombre = RECORD
Adrvect : POINTER ;
Nombre : INTEGER;
Indice_courant : INTEGER
END;
