2.0 KiB
Au delà des Automates
Nous avons vu avec le lemme de la pompe un outil permettant parfois de montrer qu'un langage n'est pas régulier. La propriété décrite par ce lemme -- le fait de pouvoir pomper -- est vraie en particulier si le langage est régulier. Quand cette propriété n'est pas vérifiée, on peut en déduire que le langage n'est pas régulier.
Établir la propriété ou sa contraposée correspond à avoir une stratégie gagnante entre deux joueurs Abélard et Éloïse.
Lorsqu'Éloïse dispose d'un automate pour le langage, elle peut utiliser l'automate pour gagner au jeu "de la pompe".
Une stratégie gagnante pour Éloïse pour le jeu dual permet de montrer que le langage n'est pas régulier.
Exo 1
Jouez au jeu de la pompe pour 2 langages. L'un qui n'est pas régulier, l'autre qui l'est.
Exo2
Choisissez Pushdown Automata et programmez un automate qui accepte les mots de la forme a^n.b^n
NB. la documentation est (ici)[https://www2.cs.duke.edu/csed/jflap/tutorial/]
Exo 3
Choisissez l'activité "Turing Machine" et proposez un programme qui accepte les mots qui commencent et terminent par la même lettre.
Dans un second temps proposer une machine de Turing qui fait des aller-retours en mangeant le extrémités égales du mots (ou rejette si différent) pour accepter les palindromes paires sur l'alphabet a,b.
Pour finir utiliser la machine de Turing à 2 rubans pour reconnaître le langage des palindromes pairs sur a,b en seulement 2n étapes environ ou n est la taille du mot d'entrée.
Exo3.
Utilisez grep pour résoudre wordle aujourd'hui.
Le dossier grep contient 3 dictionnaires :
american-english
answers.txt
wordle-allowed-guesses.txt
Le second dictionnaire comprend les mots de 5 lettres qui peuvent être solution de wordle. Le troisième comprend les mots qui ne sont pas forcément solutions mais que wordle accepte.
Wordle est un puzzle du New York Times disponible ici.