Langage / Lemme

[jeanpaul224]

Exercice 1
Soit L le langage forme des mots sur l'alphabet(a,b) qui ne contiennent pas de facteur (a,a)
1) Ecrire une expression rationelle pour L
2) Ecrire un automate fini deterministe reconaissant L
Pour la 1 j'ai quelque chose comme ça [b+|a[^a]]*
Pour la 2
j'ai quelque chose comme ça
(1) a->(2) b-> (3)
<-b <-a
(1) Ei et Ef
Avec des boucle sur b à chaque point.

Exercice 2
Soit M le langage sur l'alphabet {a,b} défini par : M ={a^n (ba)^n,n appartient à N}
En utilisant le lemme de pompage montrer que L n'est pas un langage rationnel.
Ce que j'ai fait :
Soit w= a^n (ba)^n
w1= Epsilon w2= a^n w3= ba^n
a^n = u1u2u3
=> w1u1u2^n u3
Si u2 = a^p avec p>= 1
alors a^(n+p) ba^n
Alors le langage n'est pas rationnel
(d'aprés ce que j'ia compris il faut 2x + de a que de b ce qui n'est pas le cas ici.
Je ne sais pas si ce que j'ai fait est correct ou non donc si vous avez une idée n'hésitez pas :)
(je m’entraîne sur des sujets d'examen mais si je les fais mal y'a plus trop d’intérêt ^^)