Est régulier?

J'ai passé ma théorie des examens de calcul il y a quelques semaines, et c'était l'une des questions:

Supposons que la langue$L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$

L est-il régulier? Si oui, fournissez-lui une expression régulière ou un automate.

Après que je lui ai brièvement demandé la réponse après l'examen, il semble que c'est vraiment régulier (je crois qu'il a dit que l'expression est simple ). Cependant, je n'arrive pas à comprendre pourquoi. La façon dont je le vois, sa concaténation r fois, comme ceci:$(a^*b^*)^*$$a^nb^m$

$a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$ ,

ce qui n'est pas régulier car il n'y a aucun moyen pour un automate de rappeler n et m à chaque fois. Où suis-je en faute ici?

EDIT: J'ai de nouveau parlé au professeur, il a admis que c'était une erreur. La langue n'est en effet pas régulière.

Le langage n'est pas régulier, comme le prouve la méthode de Nerode. Considérons les mots w n = a n b pour n ∈ N . Ensuite , w 2 n ∈ L , mais pour n ≠ m , w n w m ∉ L . Par conséquent, tout automate pour L doit être dans un état différent après avoir lu chaque w n , ce qui contredit sa finitude.$L$$w_n = a^n b$$n \in \mathbb{N}$$w_n^2 \in L$$n \neq m$$w_n w_m \notin L$$L$$w_n$

Dans votre commentaire, vous indiquez que vous (citation) "avez donné une réfutation du lemme de pompage pour , en disant que la même chose s'appliquait pour un r plus grand ".$r=2$$r$

Cela peut en effet être officialisé en appliquant une propriété de fermeture. Les langues régulières sont fermées sous intersection. Donc, si est régulier, alors il en serait de même pour L ∩ a ∗ b a ∗ b = { a n b a n b ∣ n ≥ 0 } , en définissant effectivement r = 2 et m = 1 .$L$$L\cap a^*ba^*b = \{ a^n b a^n b \mid n\ge 0\}$$r=2$$m=1$

La langue: {(a ⁿ b ^m ) ^r | n, m, r≥0} n'est pas régulier, car alors que l'automate / machine lit la première séquence de lettres «a» puis les lettres «b», il doit compter le nombre de fois qu'il a lu la lettre «a» et le nombre de fois où il a lu la lettre «b» dans la première séquence pour connaître la valeur de n et m .

Si r> 1, alors une autre même séquence de lettres «a» et de lettres «b» est attendue.

Si l'automate / machine ne sait pas combien de lettres 'a' et de lettres 'b' il a lues dans la première séquence, il ne connaît pas non plus la valeur de n et m et donc il ne peut pas dire si les autres séquences de l'avant-dernière au dernier sont des mots égaux à la première séquence.

Mais il est connu que seule la machine Turing peut compter et connaître les valeurs de n et m et reconnaître le langage ci-dessus, donc non seulement que le langage ci-dessus n'est pas régulier, mais même qu'il n'est pas dépourvu de contexte, c'est-à-dire aussi n'existe pas d' automate pushdown pour reconnaître cette langue et n'existe pas de grammaire sans contexte que chaque mot dérivé de cette grammaire sans contexte soit dans la langue ci-dessus.

Parce que le fait que l'automate fini déterministe et l'automate fini pushdown ne peuvent pas compter et connaître les valeurs de n et m , contrairement à la machine Turing, ils ne peuvent pas reconnaître la langue ci-dessus et donc la langue ci-dessus n'est pas sans contexte et n'est pas régulier.

Contre-exemple de l'hypothèse que la langue ci-dessus est régulière:

Pour n = 3 ∧ m = 5 ∧ r = 2 , le mot suivant est dans la langue ci-dessus:

aaabbbbbaaabbbbb

Mais le mot suivant n'est pas dans la langue:

aaabbbbbaaaaabbb, parce que ne pas exister n, m et r si:

(a ⁿ b ^m ) ^r = aaabbbbbaaaaabbb, car pour satisfaire la première séquence de lettres 'a' puis les lettres 'b', il faut être vrai que n = 3 ∧ m = 5 , et parce que l'on voit 2 séquences de lettres ' a 'puis les lettres' b ', alors r = 2 , mais si n = 3 ∧ m = 5 ∧ r = 2 alors (a ⁿ b ^m ) ^r = (a ³ b ⁵ ) ² = (aaabbbbb) ² = aaabbbbbaaabbbbbb ≠ aaabbbbbaaaaabbb, car leurs suffixes sont différents, c'est-à-dire aaabbbbb ≠ aaaaabbb, bien que leurs préfixes soient égaux à aaabbbbb pour r = 1.

Le "meilleur" automate fini déterministe qui peut être construit pour ce langage est l'automate fini déterministe qui reconnaît l'expression régulière (a * b *) *, mais il ne reconnaît pas le langage ci-dessus, car il indique que les deux mots aaabbbbbaaabbbbb et aaabbbbbaaaaabbb sont dans la langue et ce n'est pas vrai, car aaabbbbbaaabbbbb est dans la langue, mais aaabbbbbaaaaabbb n'est pas dans la langue.

Même l'automate fini pushdown ne peut pas dire si les deux mots sont dans la langue ou non, donc seule la machine de Turing le peut.

Dans la deuxième séquence, la machine de Turing a trouvé que n = 5 ∧ m = 3 et cela contredit que dans la première séquence, elle a trouvé que n = 3 ∧ m = 5 , donc elle indique que le deuxième mot n'est pas dans la langue , mais aucune contradiction ne se trouve dans le premier mot.

Les deux séquences satisfont que n = 3 ∧ m = 5 , donc la machine de Turing dit que le premier mot est dans la langue.

Seule la machine Turing peut, si elle compte et se souvient des valeurs de n et m, en écrivant leur valeur sur sa bande et en les lisant plus tard.