Je ne comprends pas le lemme de pompage pour cette déclaration, quelqu'un peut-il m'aider?Est-ce que cette grammaire {a^n b^2n | n> = 0} normal ou non?
{a^n b^2n | n> = 0}
Ceci est normal ou non? Si oui pourquoi, sinon pourquoi?
Merci à tous !!
La langue n'est pas régulière si la valeur de n est modifiée, le nombre d'états dans DFA changera également. Dans la définition de DFA pour accepter le langage régulier, l'ensemble d'états est un ensemble fini. Bien sûr, l'autre façon de le prouver comme non régulier, utiliser le lemme de pompage pour les langues régulières.
Non régulier bien sûr pour la même raison qu'un bn n'est pas régulier. Un DFA n'a pas de mémoire autre que celle-ci, donc c'est mémoire finie ... Mais je vous laisse la preuve formelle –
Ok merci, et est-ce que c'est gratuit? Merci beaucoup – niknik90
oui parce que Grammaire: S -> epsilon, S -> un S bb génère votre langue et il est de type 2 (Contexte gratuit) –