Qu'est-ce qu'une grammaire sans contexte?

104

Quelqu'un peut-il m'expliquer ce qu'est une grammaire sans contexte? Après avoir regardé l'entrée de Wikipédia, puis l'entrée de Wikipédia sur la grammaire formelle, je suis complètement perplexe. Quelqu'un aurait-il la gentillesse d'expliquer ce que sont ces choses?

Je me demande cela parce que je souhaite étudier l'analyse, et aussi sur le côté, la limitation d'un moteur regex.

Je ne sais pas si ces termes sont directement liés à la programmation ou s'ils sont davantage liés à la linguistique en général. Si tel est le cas, je m'excuse, cela pourrait peut-être être proposé si oui?

Aune
la source
2
C'est plus lié àAutomata Theorem
Rahul
2
Si vous êtes intéressé par les langages formels et la théorie des automates pour l'analyse, je vous suggère un livre comme les langages et machines de Sudkamp ou les compilateurs d' Aho, Sethi & Ullman . Chaque livre fournit une description formelle d'une grammaire sans contexte, qui est un type de grammaire formelle, puis énonce et prouve les théorèmes de base sur les grammaires sans contexte nécessaires pour les comprendre (comme le lemme de pompage pour les langages sans contexte et la conversion et théorèmes de forme normale). Il n'y a pas de prérequis mathématique pour apprendre la théorie formelle du langage au-delà d'une compréhension superficielle de la théorie des ensembles.
danportin le
1
Ces questions ne devraient-elles pas être migrées vers l'informatique théorique?
Pale Blue Dot

Réponses:

110

Une grammaire sans contexte est une grammaire qui satisfait certaines propriétés. En informatique, les grammaires décrivent les langues; spécifiquement, ils décrivent des langages formels.

Un langage formel est juste un ensemble (terme mathématique pour une collection d'objets) de chaînes (séquences de symboles ... très similaire à l'utilisation de programmation du mot "chaîne"). Un exemple simple de langage formel est l'ensemble de toutes les chaînes binaires de longueur trois, {000, 001, 010, 011, 100, 101, 110, 111}.

Les grammaires fonctionnent en définissant les transformations que vous pouvez effectuer pour construire une chaîne dans le langage décrit par une grammaire. Les grammaires diront comment transformer un symbole de départ (généralement S) en une chaîne de symboles. Une grammaire pour la langue donnée précédemment est:

S -> BBB
B -> 0
B -> 1

La façon d'interpréter cela est de dire que cela Speut être remplacé par BBB, et Bpeut être remplacé par 0, et Bpeut être remplacé par 1. Donc, pour construire la chaîne 010, nous pouvons le faire S -> BBB -> 0BB -> 01B -> 010.

Une grammaire sans contexte est simplement une grammaire dans laquelle l'élément que vous remplacez (à gauche de la flèche) est un seul symbole "non terminal". Un symbole non terminal est un symbole que vous utilisez dans la grammaire qui ne peut pas apparaître dans vos chaînes finales. Dans la grammaire ci-dessus, "S" et "B" sont des symboles non terminaux, et "0" et "1" sont des symboles "terminaux". Grammaires comme

S -> AB
AB -> 1
A -> AA
B -> 0

Ne sont pas réguliers car ils contiennent des règles comme "AB -> 1".

aegrisomnie
la source
12
Par «pas régulier», voulez-vous dire «pas sans contexte»? (car le langage représentable par les CFG est un super-ensemble de ceux représentables par des expressions régulières)
Anti Earth
3
"S peut être remplacé par B" lire "S peut être remplacé par BBB"?
Cosmo Harrigan
4
Bon seigneur, c'est l'une des meilleures réponses expliquées que j'ai vues sur SO.
Rafael Dias da Silva
1
@AntiEarth le deuxième exemple n'est pas une grammaire régulière car il a des règles qui génèrent deux symboles non terminaux à partir d'un seul symbole non terminal, ce qui n'est pas autorisé dans les grammaires régulières (également, comme OP l'a souligné, il a des règles avec plusieurs symboles non terminaux sur la gauche). en.wikipedia.org/wiki/Regular_grammar
awwsmm
21

La théorie du langage est liée à la théorie du calcul. Quel est le côté le plus philosophique de l'informatique, pour décider quels programmes sont possibles, ou lesquels seront jamais possibles à écrire, et quel type de problèmes est-il impossible d'écrire un algorithme à résoudre.

Une expression régulière est une manière de décrire un langage régulier. Un langage régulier est un langage qui peut être décidé par un automate fini déterministe.

Vous devriez lire l'article sur les machines à états finis: http://en.wikipedia.org/wiki/Finite_state_machine

Et Langues régulières: http://en.wikipedia.org/wiki/Regular_language

Toutes les langues régulières sont des langues sans contexte, mais il existe des langues sans contexte qui ne sont pas régulières. Un langage sans contexte est l'ensemble de toutes les chaînes acceptées par un Grammeur sans contexte ou un automate pushdown qui est une machine à états finis avec une seule pile: http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

Il existe des langages plus compliqués qui nécessitent une machine de Turing (tout programme possible que vous pouvez écrire sur votre ordinateur) pour décider si une chaîne est dans la langue ou non.

La théorie du langage est également très liée au problème P vs NP, et à d'autres choses intéressantes.

Mon manuel d'introduction à l'informatique de troisième année était assez bon pour expliquer ce sujet: Introduction à la théorie du calcul. Par Michael Sipser. Mais, ça m'a coûté 160 $ ​​pour l'acheter neuf et ce n'est pas très gros. Peut-être que vous pouvez trouver une copie utilisée ou trouver une copie dans une bibliothèque ou quelque chose qui pourrait vous aider.

ÉDITER:

Les limites des expressions régulières et des cours de langue supérieurs ont fait l'objet de nombreuses recherches au cours des 50 dernières années. Vous pourriez être intéressé par le lemme de pompage pour les langues régulières. C'est un moyen de prouver qu'une certaine langue n'est pas régulière:

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

Si un langage n'est pas régulier, il peut être sans contexte, ce qui signifie qu'il pourrait être décrit par un grammeur sans contexte, ou même dans une classe de langue supérieure, vous pouvez prouver qu'il n'est pas sans contexte par le lemme de pompage pour sans contexte langages similaire à celui des expressions régulières.

Une langue peut même être indécidable, ce qui signifie que même une machine de Turing (peut programmer votre ordinateur peut fonctionner) ne peut pas être programmée pour décider si une chaîne doit être acceptée comme dans la langue ou rejetée.

Je pense que la partie qui vous intéresse le plus est les machines à états finis (à la fois déterministes et déterministes) pour voir quelles langues une expression régulière peut décider, et le lemme de pompage pour prouver quelles langues ne sont pas régulières.

Fondamentalement, une langue n'est pas régulière si elle a besoin d'une sorte de mémoire ou de capacité à compter. Le langage des parenthèses correspondantes n'est pas régulier par exemple car la machine a besoin de se souvenir si elle a ouvert une parenthèse pour savoir si elle doit en fermer une.

La langue de toutes les chaînes utilisant les lettres a et b qui contiennent au moins trois b est une langue régulière: a ba ba ba

La langue de toutes les chaînes utilisant les lettres a et b qui contiennent plus de b que de a n'est pas régulière.

Il ne faut pas non plus que tous les langages finis soient réguliers, par exemple:

Le langage de toutes les chaînes de moins de 50 caractères utilisant les lettres a et b qui contiennent plus de b que de a est régulier, car il est fini, nous savons qu'il pourrait être décrit comme (b | abb | bab | bba | aabbb | ababb |. ..) ect jusqu'à ce que toutes les combinaisons possibles soient répertoriées.

Paul
la source
1
Les expressions régulières ne sont pas des programmes de décision qui correspondent aux chaînes et aux modèles. Ce sont des expressions qui désignent des ensembles réguliers, pour lesquels le problème d'appartenance est décidable.
danportin le
1
Si un ensemble est régulier, il est évidemment décidable. Je ne sais pas comment le dire autrement. Ce sont en fait des programmes de décision qui n'ont pas de mémoire.
Paul
Vous décrivez des automates finis déterministes, qui fournissent une procédure de décision pour les langages réguliers («programmes de décision qui n'ont pas de mémoire»). Les expressions régulières sont des termes qui désignent des langages réguliers, et non les programmes sont des procédures. C'était ma seule plainte.
danportin le
1
Je l'ai changé en "Une expression régulière est une manière de décrire un langage régulier. Un langage régulier est un langage qui peut être décidé par un automate fini déterministe." Est-ce que ça sonne mieux?
Paul