TD12 - Automates et Langages - RICM

Exercice 1. Quelques fonctions définis récursivement

Analyser les définitions recursives de fonctions : 

• calculer plusieurs valeurs
• trouver le schéma d'induction pour definir le domaine 
• décrire le domaine explicitement
• verifier si ce schéma est non-ambigu
• si possible, représenter la fonction explicitement

1. Bin(e)=0, Bin(x0)=2*Bin(x), Bin(x1)=2*Bin(x)+1
2. C(a)=C(b)=C(e)=C(Ø)=0, C(x*)=C(x), C((x+y))=C(x)+C(y)+1, C((xy)=C(x)+C(y)+2
3. f(0)=1, f(x+1)=(x+1)f(x)
4.  g(0)=1, g(x+1)=2^g(x) 
5. Val(a)=1, Val(b)=2,Val(+xy)=Val(x)+Val(y), Val(*xy)=Val(x)*Val(y)

Exercice 2. Quelques récursions moins évidentes

Est-il possible de faire la même chose pour les definitions suivantes

1. Bin(e)=0, Bin(x0)=2*Bin(x), Bin(0x)=2*Bin(x)+1
2. L(e)=0, L(a)=L(b)=1,L(xy)=L(x)+L(y)
3. f(0)=1, f(x)=f(x+1)/f(x)
4. si x>100, alors f(x)=x-10, sinon f(f(x+11))  (calculez f(0))

Exercice 3. Raisonnements inductifs.

1.  Prouvez par induction structurelle sur l'expression régulière qu'en renversant tous les mots d'un langage régulier on obtient un langage régulier.
2.  Prouvez par induction structurelle que Bin(x)<2 ^longueur(x) (cf. exo 2.1)

Exercice 4. Consistance et complétude

1. Montrer que le schéma {e}, x-> axb définit le langage {aⁿbⁿ | n dans N}

2. Montrer que le grammaire S->aSb,S->R,R->bRa,R->e  définit le langage {aⁿb^ma^mbⁿ}

3. Montrer que la théorie 

• Axiome : =+
• Règles d'inférence: w->|w|    et  u=v ->|u = |v 

est consistante et complète pour toutes les égalités x=y+z correctes sur les naturels /

Retour