Soit L1 et L2 deux langages non réguliers. Est-ce possible que :
1. L1 U L2 soit régulier ? Justiez
2. L1 inter L2 soit régulier ? Justiez
Merci à l'avance
-----
17/10/2013, 20h36
#2
Mocassins
Date d'inscription
mai 2012
Messages
153
Re : Automates
Si tu prends un langage sur l'alphabet A non régulier, son complémentaire dans l'ensemble des mots sur A n'est pas régulier, car sinon le complémentaire du complémentaire, qui est , serait régulier.
Et , ainsi que sont réguliers.
17/10/2013, 20h47
#3
BigL
Date d'inscription
octobre 2013
Messages
5
Re : Automates
Je ne suis pas sur de bien comprendre?
17/10/2013, 20h53
#4
Tryss
Date d'inscription
janvier 2010
Messages
3 448
Re : Automates
Envoyé par BigL
Je ne suis pas sur de bien comprendre?
Il donne un exemple de langages non réguliers tel que leur intersection et leur union est un langage régulier
Aujourd'hui
A voir en vidéo sur Futura
17/10/2013, 21h19
#5
Mocassins
Date d'inscription
mai 2012
Messages
153
Re : Automates
Oui. Il y a une coquille: il faut comprendre .
Le fait que le complémentaire d'un langage régulier soit régulier n'est je crois pas trivial et découle du théorème de Kleene.
Dernière modification par Mocassins ; 17/10/2013 à 21h22.