Pourquoi est {a^nb^n | n >= 0} n'est pas une?
Dans un CS sûr, je vais prendre un exemple d'une langue qui n'est pas régulière:
{a^nb^n | n >= 0}
Je peux comprendre qu'elle n'est pas régulière depuis pas Finite State Automaton/Machine peut être écrite qui valide et accepte cette entrée car il manque un composant de mémoire. (Corrigez-moi si je me trompe)
La l'entrée de wikipedia sur la Langue Régulier également les listes de cet exemple, mais ne pas fournir une (mathématique) de la preuve pourquoi il n'est pas régulière.
Quelqu'un peut-il m'éclairer sur ce point et fournir la preuve de ce, ou de point moi aussi une bonne ressource?
OriginalL'auteur Christophe Herreman | 2010-02-22
Vous devez vous connecter pour publier un commentaire.
Ce que vous cherchez est Lemme de pompage pour les langages réguliers.
Voici un exemple avec votre problème exact:
dernière demande a besoin de meilleures explications. Le x2yz mot peut contenir plusieurs lettres d'un tri (si y a plus de a que de b ou vice-versa), ou de dupliquer il ferait éclater la lettre de commande, dans lequel b devraient venir après tout.
incomplet de la preuve. vous n'avez pas défini de x,y,z. x a la seule limitation que | xy | <= p, où p est la longueur de pompage. vous devez vous séparer de votre preuve dans les trois cas, avec y des chaînes sur la base (a|ab|b) pour qu'il soit complet. xy pourrait consister en plus de b que de a: x=a, y=b^n, z=b
cette preuve est faux
La preuve manque certaines pièces, comme tel, il est incorrect. Plus le lien est rompu.
OriginalL'auteur cletus
Parce que vous ne pouvez pas écrire une machine à état fini ne peut "compter" les séquences identiques de 'a' et 'b' de symboles. En un mot, FSMs ne peut "compter". Essayez d'imaginer une telle FSM: combien d'états donneriez-vous à un symbole 'a'? Combien de 'b'? Que faire si votre séquence d'entrée de plus de?
Noter que si vous deviez n <= X avec X un entier de valeur vous pouvez préparer ces FSM (en ayant un seul avec un bon nombre d'états, mais encore un nombre fini); un tel langage serait régulier.
OriginalL'auteur lorenzog
Finite State Automaton n'a pas de structure de données (pile) - la mémoire comme dans le cas de la pousser vers le bas de l'automate. Ouais, ça peut vous donner quelques "a été suivie par certains" b mais pas le montant exact de "a", suivi par la pas de "b".
OriginalL'auteur Rohit Pratap