Bonjour,
Je ne savais pas où poster cet exercice, alors veuillez m'excusez si ce n'est pas au bon endroit...
J'ai du mal à comprendre les automates, ce que signifie les étoiles et comment s'y prendre.
Pouvez-vous m'aider? Merci d'avance.
Sur l'alphabet = {a,b} on considère les langages suivants :
L1 = {(ab)na n pour tout n appartenant à }
L2 = ((ab)a*)*
1. Donner la liste des mots de L1 de longueur inférieure ou égale à 5. Même question pour L2.
2. Décrire d'une phrase (ou 2) les mots de L1. Même question pour L2.
3. Soit n un entier quelconque, le mot (ab)n appartient-il à L1 ? à L2 ?
Mêmes questions pour an et pour (ab)nan
4. Montrer que L1 est inclus dans L2. A-t-on L1 = L2 ?
Salut,
Alors déjà pour un mot u, u^n signifie uuu...u n fois.
Ensuite u* est le language formé de epsilon, u, uu, uuu, uuuu, ..... c'est à dire l'ensemble des u^n pour n entier.
1/ pour L1, on a epsilon, aba, de lonngueur inférieur ou égale à 5. (pour n plus grand que 1, la longueur est 3n, supérieure à 5 donc)
pour L2, epsilon, aba, abab, abaa, abaaa, ababa. je te laisse le soin de le prouver.
2/ blabla
3/ u=(ab)^n. si u est dans L1, alors u est de la forme (ab)^m a^m. u termine par un b. donc m=0, donc n=0.
u appartient évidemment à L2 qqsoit n.
Si tu as compris le truc c'est pas bien dur de faire de même avec a^n et l'autre.
4/ inclusion : il suffit d'écrire a quoi correspond L2 = {......} et ça coule de source.
L1 = L2.... c'est assez évident si on se sert de ce qu'on a déjà fait
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :