preuve d'une langue n'est pas régulière utilisant le pompage Lemme

Question

Je suis en train de prouver que la langue suivante n'est pas régulière en utilisant le lemme de pompage.

L = {a ^k b ^3L un ^l | k ≥ 1, l ≥ 0}

J'ai décidé de choisir w = a b ^3p un ^p, puis | w | = 4p + 1 ≥ p

Des conseils?

Merci!

Answer 1

Je ne suis pas sûr de la formulation exacte du lemme de pompage que vous utilisez. En tout cas, c'est un cas plutôt délicat, parce que les formulations standard comme dans wikipedia seulement vous permettent de pomper quelque part dans un préfixe de longueur fixe. Mais votre bloc initial permet de pomper n'importe où et peut être arbitrairement long. Ainsi, vous devez utiliser une propriété supplémentaire. Je suggère deux:

• Les langues régulières sont fermées par inversion. Ainsi, vous pouvez aussi regarder $ L^R = {a^l b^{3l} a^k} $. Maintenant, tout pompage dans le bloc initial d'un sortira de la langue.
• Les langues régulières sont fermées sous l'intersection. Si vous prenez l'intersection avec un b + a + vous finissez par $ {a b^{3l} a^k} $, et maintenant le pompage dans le bloc b vous sortira de la langue.