ce qui veut dire par contexte libre pas régulier

Question

Je prépare une grammaire sans contexte pour un examen. Je ne pouvais pas comprendre pourquoi le langage

{ a^n b^n | n>=0} 

est contextuel mais pas régulier. Pourquoi n'est-ce pas régulier? Quand pouvons-nous dire qu'une expression n'est pas régulière?

Merci

Answer 1

Une expression n'est pas régulière si elle ne peut pas être adapté (exactement) par un regular expression ou (équivalente) un finite state machine. Voir également context free language et regular language.

Answer 2

Eh bien, vous pouvez dire que c'est sans contexte parce que vous pouvez l'exprimer en utilisant une grammaire sans contexte. Il n'est cependant pas régulier car une expression régulière (et des automates finis) ne peut représenter ce langage.

Answer 3

Comme dit dans les réponses précédentes, son contexte libre, car vous pouvez l'exprimer avec la grammaire sans contexte.

Par exemple: S -> aSb | ε

Ce ne est pas régulière parce que vous ne pouvez pas l'exprimer avec la machine à états finis ni des expressions régulières. Vous devriez être en mesure de compter le nombre de As et de vérifier que le nombre de Bs correspond. Cela ne peut pas être fait avec les états finis comme n pourrait être quelque chose

Answer 4

L'approche standard consiste à utiliser la Pumping Lemma