Est régulier?

9

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 langueL={(anbm)rn,m,r0}

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:(ab)anbm

anbmanbmanbm...anbmanbm ,

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.

Exci
la source
14
Vous devez demander à votre professeur si la langue est la même que la langue . S'il dit «oui», dites-lui que je vous ai dit que sa question était mal formée. K = { a n 1 b m 1 a n 2 b m 2a n r b n rr 0 , a 1 , , a r0 , b 1 , , b r0 }LK={an1bm1an2bm2anrbnrr0,a1,,ar0,b1,,br0}
Andrej Bauer
1
Cela semble être le seul moyen pour que cela puisse être régulier, et en fait, c'est ce que j'ai initialement pensé à la hâte et réellement considéré (a b ) *, mais ensuite effacé en réalisant que les n et m restent les mêmes (ou devraient ..), et a donné une réfutation de la lemme de pompage pour r = 2, disant la même chose pour un r plus grand (probablement pas exactement une solution complète non plus mais elle semble aller dans la bonne direction). Inutile de dire que j'ai obtenu 0 pour cette question. Je vais essayer de le contacter.
Je comprendrais certainement la question comme vous l'avez fait au départ.
Andrej Bauer
Voir ici pour plus de façons de montrer qu'une langue n'est pas régulière.
Raphael
vous pouvez également prouver la même chose à l'aide du pompage de la lemme
SAHIL THUKRAL

Réponses:

10

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 nL , mais pour n m , w n w mL . 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.Lwn=anbnNwn2LnmwnwmLLwn

Yuval Filmus
la source
4

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=2r

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 .LLabab={anbanbn0}r=2m=1

Hendrik Jan
la source
1
Cher lecteur, veuillez ne pas retirer "si n'est pas régulier, alors L L " n'est pas ici non plus - car c'est tout simplement faux! LLL
Raphael
1
@Raphael à droite. Donc, l'implication correcte serait "si n'est pas régulier, alors ni L ", où R est régulier. LRLR
Hendrik Jan
1
Bien sûr. Je craignais que les novices ne lisent "définir efficacement ..." et l'appliquent sans utiliser les propriétés de fermeture.
Raphael
0

La langue: {(a n 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 n 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 n b m ) r = (a 3 b 5 ) 2 = (aaabbbbb) 2 = 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.

Farewell Stack Exchange
la source