Что такое контекстно-свободная грамматика?

Может ли кто-нибудь объяснить мне, что такое контекстно-свободная грамматика? Посмотрев статью в Википедии, а затем статью о формальной грамматике в Википедии, я совершенно сбит с толку. Не мог бы кто-нибудь объяснить, что это такое?

Мне это интересно, потому что я хочу исследовать синтаксический анализ, а также, на стороне, ограничение механизма регулярных выражений.

Я не уверен, связаны ли эти термины напрямую с программированием или они больше связаны с лингвистикой в ​​целом. Если это так, прошу прощения, возможно, это можно было бы переместить, если так?

Контекстно-свободная грамматика - это грамматика, которая удовлетворяет определенным свойствам. В информатике грамматики описывают языки; в частности, они описывают формальные языки.

Формальный язык - это просто набор (математический термин для набора объектов) строк (последовательностей символов ... очень похожих на использование слова «строка» в программировании). Простым примером формального языка является набор всех двоичных строк длиной три, {000, 001, 010, 011, 100, 101, 110, 111}.

Грамматики работают путем определения преобразований, которые вы можете выполнить для построения строки на языке, описанном грамматикой. Грамматика скажет, как преобразовать начальный символ (обычно S) в некоторую строку символов. Грамматика языка, приведенного ранее:

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

Способ интерпретировать это означает , что Sможно заменить BBB, и Bможет быть заменен на 0, и Bможет быть заменен на 1. Таким образом , чтобы построить строку 010 , мы можем сделать S -> BBB -> 0BB -> 01B -> 010.

Контекстно-свободная грамматика - это просто грамматика, в которой заменяемая вами вещь (слева от стрелки) представляет собой единственный «нетерминальный» символ. Нетерминальный символ - это любой символ, который вы используете в грамматике, который не может появиться в ваших конечных строках. В грамматике выше «S» и «B» - нетерминальные символы, а «0» и «1» - «терминальные» символы. Грамматики вроде

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

Не являются регулярными, поскольку содержат правила типа «AB -> 1».

Теория языка связана с теорией вычислений. Что является более философской стороной компьютерных наук, касающейся решения, какие программы возможны или какие когда-либо можно будет написать, и какие проблемы невозможно написать алгоритм для решения.

Регулярное выражение - это способ описания регулярного языка. Регулярный язык - это язык, который может определяться детерминированным конечным автоматом.

Вам следует прочитать статью о конечных машинах: http://en.wikipedia.org/wiki/Finite_state_machine

И обычные языки: http://en.wikipedia.org/wiki/Regular_language

Все обычные языки являются контекстно-свободными языками, но есть контекстно-свободные языки, которые не являются обычными. Свободный от контекста язык - это набор всех строк, принимаемых грамматиком без контекста или автоматами выталкивания, которые являются конечным автоматом с одним стеком: http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

Существуют более сложные языки, которым требуется машина Тьюринга (любая возможная программа, которую вы можете написать на своем компьютере), чтобы решить, есть ли строка на языке или нет.

Теория языка также очень связана с проблемой P vs. NP и некоторыми другими интересными вещами.

В моем учебнике третьего курса «Введение в информатику» довольно хорошо объяснялось следующее: «Введение в теорию вычислений». Майкл Сипсер. Но мне стоило около 160 долларов, чтобы купить его новым, и он не очень большой. Может быть, вы сможете найти использованную копию или найти копию в библиотеке, или что-нибудь, что может вам помочь.

РЕДАКТИРОВАТЬ:

Ограничения регулярных выражений и более высоких языковых классов были изучены тоннами за последние 50 лет или около того. Возможно, вас заинтересует лемма о накачке для обычных языков. Это средство доказать, что определенный язык не является регулярным:

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

Если язык не является регулярным, он может быть контекстно-свободным, что означает, что он может быть описан контекстно-свободным грамматиком, или он может быть даже в более высоком языковом классе, вы можете доказать, что он не свободен от контекста, с помощью леммы перекачки для контекстно-свободного languages, который аналогичен языку для регулярных выражений.

Язык может быть даже неразрешимым, что означает, что даже машину Тьюринга (которая может запрограммировать работу вашего компьютера) нельзя запрограммировать так, чтобы она решала, следует ли принимать строку как на языке или отклонять.

Я думаю, что вас больше всего интересует конечный автомат (как детерминированный, так и детерминированный), чтобы увидеть, какие языки может определять регулярное выражение, и лемма о накачке, чтобы доказать, какие языки не являются регулярными.

По сути, язык не является регулярным, если ему нужна какая-то память или способность считать. Язык соответствующих скобок не является регулярным, например, потому что машине необходимо запомнить, открывала ли она скобку, чтобы знать, нужно ли закрывать ее.

Язык всех строк, в которых используются буквы a и b, содержащие не менее трех b, является обычным языком: a ba ba ba

Язык всех строк, использующих буквы a и b, которые содержат больше b, чем a, не является правильным.

Также не следует, что весь конечный язык является регулярным, например:

Язык всех строк длиной менее 50 символов с использованием букв a и b, содержащих больше b, чем a, является обычным, поскольку он конечно, мы знаем, что его можно описать как (b | abb | bab | bba | aabbb | ababb |. ..) и т. д., пока не будут перечислены все возможные комбинации.