Algorithmique, calculabilité et complexité

[invite1eb2a065]

Bonsoir tout le monde,

Je viens quémander de l'aide car j'ai un DM dont un exercice sur les automates finis et j'avoue n'avoir rien capter à ce chapitre :'(
La première question me donne déjà un gros mal de crâne:


Etant donnés un alphabet et un langage , on pose:
.
On dit que L est complet si et que est presque complet si \ est fini.
1°) Sur l'alphabet {a} , on pose . Donner un automate déterministe reconnaissant M.


Et là c'est le néant. Je suis juste qu'un automate déterministe possède un seul état initial et qu'il existe au plus une transition partant d'un état et portant l'étiquette b (par exemple). Je dirai aussi où je devine que l'alphabet fini = {a} mais alors après pour trouver l'ensemble fini d'états, l'état de départ, la fonction de transition, je vois vraiment pas. J'aurais vraiment besoin qu'on m'éclairement sur ce thème car pour l'instant je suis dans le noir total
Merci d'avance
-----

[imoca]

Bonjour,


m congru a 0,1,3 ou 5 modulo(6)

[invite1eb2a065]

Bonjour,
D'abord merci d'avoir répondu
Ensuite je vois à peu près comment marche la factorisation de M mais je vois pas d'où sort le avec m congru à 0,1,3 ou 5 modulo 6. De plus je ne vois pas comment on peut en déduire un automate déterministe reconnaissant M.
Je suis un pur novice dans ce chapitre donc désolé si je ne comprends pas tout d'un coup

[imoca]

m congru a 0,1,3 ou 5 modulo(6)
Les conviennent si m=2n+1 ou m=3n
donc m=2(3t)+1=6t+1 ou m=2(3t+1)+1=6t+3 ou m=2(3t+2)+1=6t+5
ou m=3(2t)=6t+0 ou m=3(2t+1)=6t+3
donc m est congru a 0,1,3,ou 5 modulo(6)
Il y a également équivalence a chaque étape du raisonnement d'ou l'égalité.

Pour créer l'automate, il va crée un automate pour chaque facteur.
Pour le facteur c'est simple: ->(1)->(2)->{(3)} ou (1) est l'état initial (3) l'état final et chaque transition est associé a la lettre "a".
Pour le second facteur: m congru a 0,1,3 ou 5 modulo(6) , crée un boucle de 6 états (0,1,2,3,4,5) tel que pour le mot on finisse sur l'état m mod[6], tu choisi les états finaux suivant se qui t'intéresse (ici m est congru a 0,1,3,ou 5 modulo(6))
Puis tu bricole les 2 automates pour en faire un seul.

[A voir en vidéo sur Futura]

[invite1eb2a065]

Je suis désolé, je n'ai pas compris pourquoi pour le facteur (), on a un automate ->(1)->(2)->(3) ...

[imoca]

->(1)->(2)->(3)->(4)->(5)->(6)->(7)->(8)-> état 3

[invite1eb2a065]

Bon décidément je ne percute toujours pas. Je ne vois pas le rapport entre les états en rouge (états sélectionnés selon le facteur j'imagine) et le facteur (). Il faut remplacer a pour trouver les états ou quelque chose comme ça pour fabriquer l'automate?
Merci d'avance

[imoca]

Les rouges sont les états finaux.

[invite1eb2a065]

oui mais pourquoi 3,4,6 et 8 ?

[imoca]

Car m congru a 0,1,3 ou 5 modulo(6) voir un des messages précédents

[invite1eb2a065]

Merci beaucoup ,cette fois j'ai compris
Dans le même exercice, j'ai une question où là c'est la galère totale

Montrez que, si L est un langage régulier sur l'alphabet {a}, alors il existe un ensemble de mots finis F, des entiers naturels i et j, et une partie k {0,1...,k - 1} tels que: . L'expression à trouver est assez impressionnante et je sais pas s'il faut utiliser un théorème comme le lemme de pompage ou autre. Si tu pourrais m'éclairer, ça serait super sympa

[imoca]

petite correction: k est une partie de [0,n-1]
Si A est un automate déterministe fini reconnaissant L, regarde la forme générale.