Scribd
Importer
286 vues1 page

Automates et Expressions Régulières

Le document présente 5 exercices portant sur la construction d'automates finis non déterministes et l'expression régulière correspondante à partir de langages formels définis sur divers alphabets. Les exercices proposent de nombreuses expressions régulières et langages formels.

Transféré par

Loubna Ennaji
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
286 vues1 page

Automates et Expressions Régulières

Le document présente 5 exercices portant sur la construction d'automates finis non déterministes et l'expression régulière correspondante à partir de langages formels définis sur divers alphabets. Les exercices proposent de nombreuses expressions régulières et langages formels.

Transféré par

Loubna Ennaji
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

Exercice II

Donner les automates des expressions régulières suivantes sur Ʃ={a, b, c}:
1) L= (aaa) ∗
2) L=a(b + ab) ∗ + b ∗ (a + bb).
3) L = {w ∈ {a, b, c} ∗ | |w|a = |w|b + |w|c}
4) L= 𝑎𝑖 𝑐𝑏 𝑖 i ∈ ]0,+∞[
5) L= 𝑎𝑖 𝑐𝑏 𝑗 avec i<j.

Exercice III
Donner l’expression régulière et l’AFN engendré par les langages :
1) Le langage L1 sur Ʃ={a, b, c}, des mots qui se composent des a suivie des b et qui se
terminent par a, ou des séquences de ba.
2) Des mots binaires qui commencent par 1 et comportent des séquences de 101 et accepte
la division sur 4.
3) Des mots sur Ʃ={a, b, c} dont la longueur est inférieur à 6.
4) Des entiers naturels qui acceptent la division sur 3.
5) Des entiers naturels appartenant à l’intervalle [1,999]
6) Des entiers naturels signés qui acceptent la division sur 2.
7) Des entiers naturels signés inférieur à 1000.
8) Le langage L1 sur Ʃ={a, b, c} tel que L=a ( (a b) ∗ c b∗ ) ∗ + a ( (b a) 2 c b∗ ) ∗
Exercice IV
Donner les expressions régulières et Ʃ à partir des automates suivants

Vous aimerez peut-être aussi