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

Question

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

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

Answer 1

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

Формальный язык - это просто набор (математический термин для набора объектов) строк (последовательности символов ... очень похожий на использование слова "строка" в программировании). Простым примером формального языка является набор всех двоичных строк длины три {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".

Answer 2

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

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

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

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

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

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

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

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

EDIT:

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

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

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

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

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

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

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

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

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

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