5 Questions
Quel est lebut à atteindre dans le système de règles de transformations portant sur l'alphabet A, B, C?
A C
Quel est le rôle de la lettre dans les règles de transformations?
Elle représente une chaîne quelconque de lettres de l'alphabet initial
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?
Supprimer des lettres à la chaîne
Quel est le résultat de la pose k = b (mod 3) dans le problème?
k est égal à b modulo 3
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.
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.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
