Formal Language Transformation Rules

Quel est lebut à atteindre dans le système de règles de transformations portant sur l'alphabet A, B, C?

Quel est le rôle de la lettre  dans les règles de transformations?

Quel est le résultat de l'application de la règle R4 à la chaîne C?

Quel est le sens de la réduction du problème à supprimer un B?

Quel est le résultat de la pose k = b (mod 3) dans le problème?

Système de règles de transformations

Le système de règles de transformations porte sur l'alphabet A, B, C avec quatre règles R1, R2, R3 et R4.
R1: α B α → B C (remplacement de B par C)
R2: A α A α → α (suppression de A)
R3: B B B → B C (remplacement de B par C)
R4: C → ε (suppression de C)

Donnée de départ et but à atteindre

La donnée de départ est A B.
Le but à atteindre est A C.

Représentation du graphe des états possibles

Il est possible de représenter le graphe des états possibles du problème car il existe un nombre fini d'états.

Suppression d'un B

Le problème se ramène à supprimer un B.
En désignant par b le nombre de B dans les chaînes formées, le problème peut être reformulé : " Comment supprimer un B ?"
Le but est atteignable car il est possible de supprimer un B en appliquant les règles de transformations.

Représentation par k = b (mod 3)

Une autre représentation consiste à poser k = b (mod 3).
Le problème peut être reformulé : "Comment atteindre k = 0 (mod 3) ?"
Les états possibles pour k sont 0, 1 et 2.

Analyze a system of transformation rules on the alphabet A, B, C. Given the initial state A B, determine if it's possible to reach the goal state A C using the rules R1, R2, R3, and R4. Explore the graph of possible states and think about suppressing a B.