TD MI1 Complexite Td Turing

7/23/2019 TD MI1 Complexite Td Turing

1/3

Universit des Antilles GuyaneUFR Science - Dpartement Mathmatique et Informatique

Master Informatique 2011-2012

1

Complexit

Fiche TD : machines de TringExercice 1:

Dcrire une machine de Tring qui ajoute 1 une squence de 1.

Exercice 2 :

Dcrire une machine de Tring qui fait la somme de deux nombres cods par des 1 et sparspar un espace

Exercice 3:

Dcrire une machine de Tring reconnaissant le langage suivant {anbn| n>=0}

Exercice 4 :

Dcrire une machine de Tring reconnaissant le langage suivant {a2^n

| n>=0}

Exercice 5 :

Dcrire une machine de Tring reconnaissant le langage suivant {ww | w = {0,1}*}

Exercice 6: (examen 2007-2008)

Dcrire une machine de Tring reconnaissant le langage suivant {anbncn| n>1}

Exercice 7 :

Dcrire une machine de Tring permettant de dupliquer un mot.

Exercice 8 : Machine de Tring (examen 2008-2009)Dcrire une machine de Tring qui lit une squence continue de caractres 1 et 0 (par ex010011110101101) et sarrte dans un tat qi si le nombre de 1 lus est impair, et qp si lenombre de 1 lus est pair.

Exercice 9 : Machines de Tring (examen 2006-2007)

Soit la machine de Turing M=(Q, , , , q0, #, ) avec :

Q={q0, q1, q2, q3}, ={a, b, A, A', B, B', #}, ={a, b} et

dfinie par :

(q0,a) (q1,A',R) (q0,b) (q3,B',R)

(q1,a) (q1,a,R) (q3,a) (q3,a,R)

(q1,b) (q1,b,R) (q3,b) (q3,b,R)

(q1,A) (q1,A,R) (q3,A) (q3,A,R)

(q1,B) (q1,B,R) (q3,B) (q3,B,R)

(q1,#) (q2,A,L) (q3,#) (q2,B,L)

(q2,a) (q2,a,L) (q2,b) (q2,b,L)


2/3



2

(q2,A) (q2,A,L) (q2,B) (q2,B,L)

(q2,A') (q0,A,R) (q2,B') (q0,B,R)

1. Donner la suite des configurations de M obtenues pour le mot d'entre abb.

2.

Quel est le contenu du ruban aprs excution de M sur le mot abab ?3. Quel langage M dcide-t-elle ? Quelle fonction M calcule-t-elle ?


Dcrire une machine de Tring permettant de vrifier quun systme de parenthses estcorrect.

(), (()()), ((())) sont corrects,

)()), ((), ( sont incorrects.Vous pouvez dans un premier temps donner lalgorithme permettant de vrifier le systme deparenthsage. Puis donner la machine de Tring par des rgles ou une machine tats finis.

Exercice 11: Machines de Tring (examen 2007-2008)Soit la machine de Turing M=( , Q, q0, Q, ) avec :

={a, b, c, d, #} Q={q0, q1, q2, q3, q4, q5, q6,qOui, qNon}, q0 = q0 Q = { qOui, qNon} :

q a B c d # A0 1,A,D 6,b,D 6,c,D 6,d,D Oui,#,D1 1,a,D 2,b,D 2,b,D 2,b,D Non,#,D Non,A,D2 3,a,D 2,b,D 2,b,D 2,b,D Non,#,D Non,A,D

3 3,a,D Non, b,D Non, c,D Non, d,D 4, #,G 4, A, G4 5,A,G

5 5,a,G 5,b,G 5,c,G 5,d,G 0,A,D6 Non,a,D 6,b,D 6,c, D 6, d, D Oui,#,D Oui,A,D

4. Donner la suite des configurations de M obtenues pour les mots d'entre abca,aabdcaa, ababa

5. Quel langage M dcide-t-elle ?

Exercice 12 : Machine de Tring (examen 2008-2009)

Soit la machine de Turing M = ( , Q, q0, Q, ) avec : ={a, b, c, #}, Q={q0, q1, q2, q3, q4,qOui, qNon}, q0 = q0, Q = { qOui, qNon}, :Q a b C A B C #

0 1, A, D Non, b, D Non, c, D 4, C, D Oui, #, D1 1, a, D Non, b, D 2, C, D Non, B, D 1, C, D Non, #, D2 Non, a, D 3, B, G 2, c, D 2, B, D Non, #, D

3 3, a, G 3,b, G 3, c, G 0, A, D 3, B, G 3, C, G4 Non, a, D Non, b, D Non, c, D 4, B, D 4, C, D Oui, #, D

1.

Donnez la suite des configurations de M obtenues pour les mots d'entre acb, aacbb2. Quel langage M dcide-t-elle ?


3/3



3


Soit la machine de Turing M = ( , Q, q0, Q, ) avec : ={a, b, c, #}, Q={q0, q1, q2, qF,qV}, q0 = q0, Q = { qFi, qV }, :

Q a B C x #q0 q1, a, D q1, b, D q1, c, D qF, x, D qV, #, D

q1 q1, a, D q1, b, D q1, c, D q2,x,D qF, #, Dq2 q2, a, D q2, b, D qF, c, D qF,x,D qv, #, D

1. Donnez la suite des configurations de M obtenues pour les mots d'entre abxabc,abcxab


Exercice 14 : machines de Tring (examen 2010-2011)

Dcrire une machine de Tring qui reconnait le langage suivant : L = {(abc)n| n0 } partirde lalphabet = {a, b ,c}

Exercice 15 : machines de Tring (examen 2010-2011)

Dcrire une machine de Tring qui prend en entre un mot de la forme {an1bn2} et qui sortdans ltat Qegal si n1= n2, Qsup si n1> n2, et Qinf si n1< n2

Exercice 16 : machine de Tring (examen 2010-2011)

Soit la machine de Turing M = ( , Q, q0, Q, ) avec : ={0, 1, #}, Q={q0, q1, q2, qF, qV},q0 = q0, Q = { qF, qV }, :

Q 0 1 #

q0 q1, 0, D qF, 1, D qV, #, Dq1 qF, 0, D q2, 1, D qF, #, Dq2 qF, 0, D q0, 1, D qF, #, D

1. Donnez la suite des configurations de M obtenues pour les mots d'entre 0110111,011011


Exercice 17 : machine de Tring(examen 2010-2011)Dcrire une machine de Tring qui reconnait le langage suivant : L = {an1bn2cn3 |

0

Documents

TD MI1 Complexite Td Turing