Preuves utilisant le lemme de pompage régulier

8

J'ai deux questions:

  1. Je considère la langue suivante

    L1={w{0,1}u{0,1}:w=uuR}.
    En d'autres termes wn'est pas palindrome de même longueur. J'ai prouvé que ce langage n'est PAS régulier en prouvant que son complément n'est pas régulier. Ma question est de savoir comment le prouver en utilisant le lemme de pompage sans passer par le complément.
  2. Laisser

    L2={w{0,1}w has same number of 101 substrings and 010 substrings}.
    J'ai prouvé que ce langage n'est pas régulier en utilisant des classes d'équivalence. Comment puis-je le prouver en utilisant le lemme de pompage?

Merci beaucoup pour l'édition :)

farseer
la source
Remarque. Mon navigateur n'affiche pas le signe "n'existe pas" dans la description deL1. Ne vous inquiétez pas: il est là dans la source, et changer de navigateur a aidé.
Hendrik Jan

Réponses:

7

Toutes les langues non régulières ne réussissent pas le test du lemme de pompage. Wikipédia a un exemple extrêmement complexe d'une langue non régulière qui peut être pompée. Donc, même si une langue n'est pas régulière, nous ne pourrons peut-être pas prouver ce fait en utilisant le lemme de pompage.

Mais il s'avère que nous pouvons utiliser le lemme de pompage pour prouver que votre langue maternelle n'est pas régulière. Je ne suis pas sûr de la seconde.

Prétendre: L1 n'est pas régulier.

Preuve: par le lemme de pompage. Laisserpêtre la longueur de pompage. (Je vais utiliser l'alphabet{a,b} plutôt que {0,1}.) Si p=1, puis prenez la chaîne abbaa, lequel est dedans L1 et le pomper aabbaa qui n'est pas en L1, donc L1 ne serait pas régulier.

Si p>1, puis prenez la chaîne apbbaN. (Nous trouverons ce que nous voulonsN être plus tard.) Considérez ensuite toute division de la chaîne en xyzx=apk, y=ak, et z=bbaN.

Maintenant, pompons cette chaîne ifois. (Nous trouverons ce que nous voulonsi être plus tard.) Nous obtenons la chaîne xyiz, qui donne apkaikbbaN=apk+ikbbaN.

Maintenant, revenons en arrière. Tout d'abord, nous avons choisiN. Ensuite, un choix deka été faite. Ensuite, nous avons choisii. Nous voulons comprendre ce queN choisir de telle sorte que, pour tout choix de k[1,p], nous pouvons choisir un i qui fait de cette chaîne un palindrome en faisant le nombre de as à gauche est égal au nombre à droite. (Il aura toujours une longueur égale.)

Nous voulons donc toujours obtenir cela pk+ik=N. Si nous jouons avec les mathématiques, nous constatons que nous devons choisirN=p+p! et choisissez i=p!/k+1.

Donc, pour récapituler, nous avons choisi N=p+p! et a choisi la chaîne apbbaN. Ensuite, un choix dek a été fait pour que la chaîne soit composée de apkybbaNy=ak. Ensuite, nous avons choisii=p!/k+1. Nous avons pompé la chaîne pour obtenirapkyibbaN=apkaikbbaN=apk+ikbbaN.

Mais nous savons que pk+ik=pk+(p!k+1)k=pk+p!+k=p+p!. EtN=p+p!. Donc, le nombre deas aux deux extrémités est le même, donc la chaîne est un palindrome de longueur égale, donc ce n'est pas dans L1, donc L1 n'est pas régulier.

usul
la source
Réponse parfaite!
farseer
Merci beaucoup pour votre aide. L'idée veut choisir judicieusement la chaîne.
farseer
J'aurais aimé vous donner une réponse dans les deux langues, mais la seconde a l'air douloureuse! L’approche qui m’a conduit à la réponse de la première essayait de prouver queL1est en fait pompable - quand je suis arrivé au dernier cas et que je n'ai pas pu le prouver, j'ai pu commencer à voir comment construire la chaîne ci-dessus.
usul
@usul comment êtes-vous arrivé à ceci: N=p+p!, i=p!/k+1i=p!/k+1?
Dima Knivets
3

Pour la première question, la chaîne 0p12p0p+p!est un contre-exemple approprié. Quelle que soit la durée dey est, il doit être un facteur de p!donc on pompe assez et on obtient p+p! zéros au début.

Luke Mathieson
la source
1

Après une longue réflexion, je pense avoir répondu 2.

nous choisissons la chaîne (010) ^ N (101) ^ N, où N est la longueur de pompage. Peu importe ce que nous choisirons, xy ^ 0z aura plus de 101 que de 010. L'idée est que nous ne pouvons ajouter que 101 sous-chaînes supplémentaires dans la première partie de la chaîne ou supprimer quelques sous-chaînes de 010.

farseer
la source
Malheureusement, cela ne semble pas fonctionner :( La chaîne 010010101101 (N = 2) a trois (!) Occurrences de chacune. En supprimant la troisième lettre, nous obtenons 01010101101, qui a encore trois occurrences de 010. Attention au chevauchement. Je suis toujours perplexe. ...
Hendrik Jan
Oui! Mais nous avons 4 occurrences de 101! Et donc quantité de 101 sous-chaînes! = Quantité de 010
farseer
Oops. Désolé. J'aurais dû lire ce que vous avez dit exactement: "ajouter plus de 101 sous-chaînes". +1 (dossier clos)
Hendrik Jan