Podcast
Questions and Answers
Quel est lebut à atteindre dans le système de règles de transformations portant sur l'alphabet A, B, C?
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ô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 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 sens de la réduction du problème à supprimer un B?
Signup and view all the answers
Quel est le résultat de la pose k = b (mod 3) dans le problème?
Quel est le résultat de la pose k = b (mod 3) dans le problème?
Signup and view all the answers
Study Notes
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.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
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.