(:comparaision de chaînes, analyse de mots d'une grammaire:)

TP RdF, semaine 12: chaînes, langages et grammaires

Ce TP est réalisé dans l'environnement Prolog.

Distance de chaînes

A la main

A l'aide de l'algorithme naïf vu en cours, calculez la distance edit entre les deux chaînes suivantes:

- excused

- exhausted

Sur machine

Dans l'environnement Prolog, chargez le fichier levenshtein.pl fourni dans l'archive. Ce fichier contient une implémentation en Prolog de la distance de Levenshtein.

L'utilisation est la suivante : levenshtein(mot1, mot2, D), où D est l'inconnue à déterminer.

1. Utilisez cette implémentation pour déterminer la distance entre les deux mêmes mots précédents.

2. Considérez les exemple d'apprentissage suivant sur l'alphabet ternaire A = {a,b,c} :

classe 1classe 2classe 3
aabbcbccbacaaaa
ababccbbbcacbcaab
babbcccbbaaaabaaca

Utilisez la distance edit pour classifier chacune des chaînes suivantes (en cas d'ambiguité, précisez quelles sont les catégories candidates) :

- "abacc"

- "ccab"

- "ccbba"

- "bbaaac"

Arbre de dérivation pour une grammaire

A la main : la grammaire G

Considérez la grammaire G:

  - Alphabet A = {a,b,c}
  - Axiome = S
  - Non-terminaux = {A,B}
  - Règles de production P =
S --> cAb
A --> aBa
B --> aBa
B --> cb

1. De quel type est cette grammaire?

2. Montrez que cette grammaire génère le langage L(G) = {ca^ncba^nb|n>=1}

3. Dessinez les arbres de dérivation des chaînes suivantes:

  - "caacbaab"

  - "cacbab"

Sur machine : les palindromes

Un palindrome est une séquence de caractères qui se lit de manière identique de gauche à droite ou de droite à gauche. Par exemples, "bob", "otto", "esoperesteicietserepose" sont des palindromes.

1. Construisez une grammaire qui génère tous les palindromes avec les 26 lettres de l'alphabet (sans espace). Dessinez un arbre de dérivation pour "bob" et "otto".

2. De quel type est cette grammaire?

3. Implémentez cette grammaires avec Prolog et vérifier que "esoperesteicietserepose" est un palindrome à l'aide de votre implémentation.