Podcast
Play an AI-generated podcast conversation about this lesson
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?
- B C
- A C (correct)
- A B
- C A
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?
- Elle représente la chaîne vide
- Elle représente un état possible
- Elle représente une chaîne quelconque de lettres de l'alphabet initial (correct)
- Elle représente un élément de l'alphabet
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?
- C
- A
- (correct)
- B
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.
