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

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?

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".

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.