B = {1^k y | k >= 1, y in {0, 1}* and y contains at least k 1's }
Cette langue est-elle régulière? Si oui, comment le prouvez-vous, et comment le représenteriez-vous avec une expression régulière en Python?Est-ce une langue normale? Si oui, quelle est l'expression régulière?
Ceci est pour le travail en classe, donc si vous pouviez expliquer les raisons et les processus derrière votre réponse, ce serait très apprécié.
La langue que vous avez est équivalent à cette langue:
B' = {1 y | y in {0, 1}* and y contains at least one 1}
Vous pouvez prouver que B « est sous-ensemble de B, puisque la condition B » est le même que B, mais avec k mis à 1 Prouver B est un sous-ensemble de B 'implique de prouver que tous les mots dans B où k> = 1 appartient aussi à B', ce qui est facile, puisque nous pouvons enlever le premier 1 dans tous les mots dans B et y Pour être le reste de la chaîne, y en contiendra toujours au moins un. Par conséquent, nous pouvons conclure que B = B'.
Notre travail est simplifié pour assurer le premier caractère est 1 et il y a au moins 1 1 dans le reste de la chaîne.
L'expression régulière (la notation CS) sera:
10*1(0 + 1)*
Dans la notation utilisée par les moteurs regex communs:
10*1[01]*
Le DFA:
Ici q2 est un état final.
"Au moins" est la clé pour résoudre cette question. Si le mot devient "égal", alors l'histoire sera différente.
@GrijeshChauhan: Quel est votre contre-exemple? – ibid
@nhahtdh mettre à jour votre réponse afin que je puisse voter.vous êtes correct un plus [question connexe est ici.] (http://stackoverflow.com/questions/14521300/why-l-wxwr-wx-belongs-to-ab-is-a-regular-language) –
@GrijeshChauhan : Mise à jour ** quoi **? – nhahtdh
Nous n'avons pas encore étudié les langues sans contexte - comment pouvez-vous dire cela? – camdroid
Ce n'est pas normal, car vous ne pouvez pas stocker une taille arbitraire 'k' dans un nombre fini d'états. Pour une démonstration formelle, utilisez le lemme de pompage. – starblue
@starblue - Le lemme de pompage n'est-il pas nécessaire mais pas suffisant? – camdroid