Inscription / Connexion Nouveau Sujet
Niveau Licence Maths 1e ann
Partager :

exercice automates finis déterministes

Posté par
tinybond1
27-03-09 à 12:57

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 ?

Posté par
remycmoi
re : exercice automates finis déterministes 27-03-09 à 14:01

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 :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !