les languesQuelle est l'intersection de deux langues?
Étant donnéL1={anb2m|n,m≥1}
L2={anb3n|n≥0}
L = L1 ∩ L2
Je sais que L1 est la langue régulière et L2 peut être représenté par un PDA. Mais je ne comprends pas la réponse qui indique que L est {a2nb6n|n≥1}. Comment cette solution a-t-elle été calculée?
Un langage est juste un ensemble (de chaînes valides), donc ce que nous avons ici est vraiment juste un simple problème dans l'arithmétique entière. Il suffit d'enlever le costume élégant des langues formelles pour arriver à l'essence du problème. Les deux ensembles L1 et L2 sont des sous-ensembles de {acount(a)bcount(b)|j,k≥0}; c'est-à-dire qu'ils consistent en un certain nombre de et s suivis d'un certain nombre de b s. La condition pour L1 limite count(b) à un nombre pair positif, car il doit être 2m pour un nombre entier m≥1. La condition pour L2 limite count(b) pour être exactement 3×count(a).
Maintenant, l'intersection de deux ensembles définis avec des prédicats est l'ensemble des éléments tels que les deux prédicats sont vrais. Donc count(b) doit être divisible par 2 et par 3, ce qui signifie qu'il doit être divisible par 6; en d'autres termes, il doit être 6n pour un nombre entier positif n. Et cela signifie que count(a) doit être 2n car il y en a exactement trois fois plus b s. Cela vous donne la réponse fournie.
Comme L2, L n'est pas régulier, mais il peut être implémenté avec un PDA très similaire.
Copie possible de [Quelle est l'intersection de deux langues avec des alphabets différents?] (Http://stackoverflow.com/questions/15213955/what-is-the-intersection-of-two-languages-with-different- alphabets) – veganaiZe
@rici c'est exactement ce que je ne comprends pas à ce sujet, 'L' est fondamentalement la solution fournie – totoro
@totoro: OK, j'ai essayé d'éditer votre question pour clarifier votre point de confusion. Des questions comme celle-ci devraient être posées sur http://cs.stackexchange.com/, car elles n'ont rien à voir avec la programmation. Cependant, sachez que votre question ne sera pas bien reçue à moins que vous n'essayiez de montrer votre travail. – rici