Глава 13 контекстно свободные грамматики


Содержание

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

Доброго времени суток.

Есть программа, реализующая проверку принадлежности цепочки к Право линейной грамматике:

13.12.2015, 11:28

С++ является контекстно независимым языком по иерархии Хомского?
С++ является контекстно независимым языком? Можете привести пример контекстно-зависимого языка?

Контекстно-свободная грамматика
Поясните пожалуйста за Контекстно-свободную грамматику. (или посоветуйте чтиво, где доходчиво.

Контекстно-свободная грамматика
Дня доброго всем. Не могли бы вы построить контекстно-свободную грамматику, для языка L, если L =.

В словах “килограм”, “граматика”, “грамофон” исправить грамматические ошибки
Помогите пожалуйста, В словах “килограм”, “граматика”, “грамофон” исправить грамматические.

Свободная память пк
Вводится одномерный массив У меня есть такой пункт: Размер массива также задается.

Глава 13 контекстно свободные грамматики

Взвешенная контекстно-свободная грамматика — Связать? Взвешенная контекстно свободная грамматика (ВКС грамматика) это контекстно свободная грамматика, у которой каждому правилу вывода соответствует числовой вес. Вес дерева раз … Википедия

Контекстно-зависимая грамматика — (КЗ грамматика, контекстная грамматика) частный случай формальной грамматики (тип 1 по иерархии Хомского), у которой левые и правые части всех продукций могут быть окружены терминальными и нетерминальными символами. Частным случаем… … Википедия

Контекстно-свободные — Контекстно свободная грамматика (КС грамматика, бесконтекстная грамматика) частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно свободная»… … Википедия

Контекстно-свободный язык — Контекстно свободная грамматика (КС грамматика, бесконтекстная грамматика) частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно свободная»… … Википедия

Грамматика формальная — Формальная грамматика или просто грамматика в теории формальных языков способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавитa. Различают порождающие и распознающие (или… … Википедия

ГРАММАТИКА БЕСКОНТЕКСТНАЯ — грамматика контекстно свободная, КС грамматика, грамматика составляющих, все правила к рой имеют вид где А вспомогательный символ и непустая цепочка (так наз. бесконтекстные правила). Языки, порождаемые такими грамматиками, наз. бесконтекстными… … Математическая энциклопедия

Бесконтекстная грамматика — Контекстно свободная грамматика (КС грамматика, бесконтекстная грамматика) частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно свободная»… … Википедия

КС-грамматика — Контекстно свободная грамматика (КС грамматика, бесконтекстная грамматика) частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно свободная»… … Википедия

DC-грамматика — Грамматика, построенная на определённых предложениях (сокр. DC грамматика, DCG; от англ. Definite clause grammar) это способ построения грамматики в логических языках программирования, например, Пролог. DC грамматика обычно… … Википедия

Контекстно-свободные грамматики

15.1. Общий алгоритм разбора

Чтобы определить то, что называют контекстно-свободной грамматикой (КС- грамматикой ), надо:

  • указать конечное множество , называемое алфавитом ; его элементы называют символами ; конечные последовательности символов называют словами (в данном алфавите );
  • разделить все символы алфавита на две группы: терминальные («окончательные») и нетерминальные («промежуточные»);
  • выбрать среди нетерминальных символов один, называемый начальным ;
  • указать конечное число правил грамматики , каждое из которых должно иметь вид , где — некоторый нетерминальный символ , а — слово (в него могут входить и терминальные, и нетерминальные символы ).

Пусть фиксирована КС- грамматика (мы часто будем опускать префикс «КС-«, так как других грамматик у нас не будет). Выводом в этой грамматике называется последовательность слов , в которой состоит из одного символа, и этот символ — начальный, а получается из заменой некоторого нетерминального символа на слово по одному из правил грамматики . Слово , составленное из терминальных символов, называется выводимым , если существует вывод , который им кончается. Множество всех выводимых слов (из терминальных символов ) называется языком , порождаемым данной грамматикой >.

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

Пример 1. Алфавит :

Примеры выводимых слов:

Пример 2. Другая грамматика , порождающая тот же язык:

Алфавит : ( ) [ ] T E

Для каждого нетерминального символа можно рассмотреть множество всех слов из терминальных символов , которые из него выводятся (аналогично тому, как это сделано для начального символа в определении выводимости в грамматике ). Каждое правило грамматики можно рассматривать как свойство этих множеств. Покажем это на примере только что приведенной грамматики . Пусть и — множества слов (из скобок), выводимых из нетерминалов T и E соответственно. Тогда правилам грамматики соответствуют такие свойства:

E E содержит пустое слово
E-> TE если слово A принадлежит T , а слово B принадлежит E , то слово AB принадлежит E
T->[E] если A принадлежит E , то слово [A] принадлежит T
T->(E) если A принадлежит E , то слово (A) принадлежит T

Сформулированные свойства множеств , не определяют эти множества однозначно (например, они остаются верными, если в качестве и взять множество всех слов). Однако можно доказать, что множества , задаваемые грамматикой , являются минимальными среди удовлетворяющих этим условиям.

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

15.1.2. Построить грамматику , в которой выводимы слова

(а) 00..0011..11 (число нулей равно числу единиц);

(б) 00..0011..11 (число нулей вдвое больше числа единиц);

(в) 00..0011..11 (число нулей больше числа единиц);

15.1.3. Доказать, что не существует КС- грамматики , в которой были бы выводимы слова вида 00..0011..1122..22 , в которых числа нулей, единиц и двоек равны, и только они.

Указание. Доказать следующую лемму о произвольной КС- грамматике : для любого достаточно длинного слова , выводимого в этой грамматике , существует такое его представление в виде , что любое слово вида , где и повторены одинаковое число раз, также выводимо в этой грамматике . (Это можно установить, найдя нетерминальный символ , оказывающийся своим собственным «наследником» в процессе вывода.)

Нетерминальный символ можно рассматривать как «родовое имя» для выводимых из него слов. В следующем примере для наглядности в качестве нетерминальных символов использованы фрагменты русских слов, заключенные в угловые скобки. (С точки зрения грамматики каждый такой фрагмент — один символ!)

Теория контекстно-свободных языков (КС-языков)

ТЕОРИЯ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ

Изучим сначала частный случай контекстно-свободных языков:

автоматные языки (А-языки), тесно связанный с простейшими схемами

преобразования строчной информации: конечными автоматами.

Конечные автоматы предназначены для чтения и порождения

формальных языков, называемых автоматными.

Конечные автоматы — это математические схемы, выполняющие

анализ и преобразование цепочек символов. Автоматы, выполняющие

только анализ (распознаватели), называются автоматами б е з в ы х о д а (без входа), или автоматами Мура (Moore finite machines).

Конечные автоматы — преобразователи называются автоматами

с о в х о д о м и в ы х о д о м или автоматами Мили

(Mealey finite machines). Автоматы со входом и выходом реализуют некоторую функцию на словах (возможно, неоднозначную)

Конечный автомат состоит из устройства управления (УУ),

головки и ленты. Автомат работает над словами, записанными на

ленте. Головка автомата видит (читает или пишет) ровно один символ.

Автомат работает п о т а к т а м и за каждый такт читает ровно один символ. При чтении очередного символа автомат (вообще говоря) меняет состояние.

Cхема автомата Мура (без выхода)

Автомат имеет одну (входную) ленту. Пустые ячейки ленты

в х о д н о е с л о в о # # # # # # # # # # # # # # #

Головка автомата читает букву х Лента движется на одну позицию

вправо за каждый такт (шаг)

Схема автомата Мили

Автомат имеет две ленты — входную и выходную

a b c x e f g h # # # # # # # # # # # # # # #

(этот автомат переводит латинские буквы в русские).

Автомат Мили читает символы по одному за такт, а пишет за такт

столько символов, сколько указано в команде; например, вместо h

может писать эйч.

Как автомат Мура, так и автомат Мили, в начале работы

автомат находится в начальном с о с т о я н и и. Будем обозначать его

На каждом шагу автомат читает один (и только один) символ, находит

п о д х о д я щ у ю к о м а н д у в списке команд автомата и

переходит в другое (вообще говоря) состояние. Если подходящей ко-

манды не находится, то говорят, что автомат не допускает слова.

Конечным автоматом K называется четверка (A, S, SF, P),

где A — алфавит автомата, S — множество состояний автомата

(конечное непустое), SF — подмножество S, называемое множеством

ф и н а л ь н ы х (заключительных) состояний, P — множество

команд (конечное непустое). Команды имеют форматы

для автоматов без выхода:

Sn a → Sm либо Sn a → пусто,

Sn a → Sm x либо Sn a → пусто .

Здесь n и m — номера состояний автомата, а — читаемый

символ, х — (конечная, возможно пустая) цепочка символов,

которую пишет автомат.

Команды с пустой правой частью определяют финальное

множество состояний («свободные” выходы).

Замечание. Конечные автоматы без выхода на каждом шагу читают (стирают с ленты) один символ, автоматы со входом и выходом читают (стирают с ленты) ровно один символ и пишут на ленту цепочку х (возможно пустую).

Определение. Пара (Sn, a), где Sn — состояние, а — буква алфавита A, называется с и т у а ц и е й, в которой находится автомат.

Совокупное состояние УУ и ленты автомата называется

к о н ф и г у р а ц и е й.

Говорят, что автомат K п р и м е н я е т с я к слову x

если в начальной конфигурации

(1) автомат К находится в состоянии S1;

(2) автомат читает первый (слева) символ слова х, либо он читает

(пустой) признак конца слова (символ #). В этом втором варианте

говорят, что автомат применяется к пустому слову L.

Говорят, что автомат К д о п у с к а е т слово (или, иначе, ч и т а е т слово), если в результате выполнения его команд он приходит в финальное состояние когда слово прочитано до конца

(читается правый ограничитиель).

Формально конечные автоматы без выхода можно рассматривать и

как читающие устройства, и как пишущие. Для пишущих автоматов

команды имеют вид

Sn → Sm а либо Sn → пусто.

Эти автоматы – недетерминированные, и п о р о ж д а ю т

множество слов, которые допускают соответствующие конечные

автоматы без выхода. Они эквивалентны а в т о м а т н ы м

г р а м м а т и к а м, описанным в следующем разделе.

. Последовательность конфигураций начиная от начальной и

кончая остановкой автомата называется протоколом.

П р и м е р 1. Автомат К1 без выхода с командами

читает слово х = abab.

конфигурация подходящая команда

S1 3 — нормальный останов

Таким образом, автомат К1 допускает х=abab

Тот же автомат не допускает слова x=aba

П р и м е р 2. Автомат Мили К2 подавляющий левые нули.

Команды автомата К2:

Пусть К2 означает функцию, реализуемую конечным автоматом К2.

K2 (0001011) = 1011

K2 (012) = ? — нет подходящей команды.

Форматы команд конечного автомата

для автоматов без выхода:

Sn a → Sm либо Sn a → пусто,


Sn a → Sm x либо Sn a→ пусто.

Здесь n и m — номера состояний автомата, а — читаемый

символ, х – (конечная, возможно пустая) цепочка символов,

которую пишет автомат.

Команды с пустой правой частью определяют финальное

множество состояний («свободные” выходы).

Замечание. Конечные автоматы без выхода на каждом

шагу читают (стирают с ленты) один символ, автоматы со входом

и выходом читают (стирают с ленты) ровно один символ и пишут

на ленту цепочку х (возможно пустую).

Определение. Пара (Sn, a), где Sn — состояние,

а — буква алфавита А, называется с и т у а ц и е й, в которой

находится автомат. Совокупное состояние УУ и ленты автомата

называется к о н ф и г у р а ц и е й.

Говорят, что автомат K п р и м е н я е т с я к слову x если

в начальной конфигурации

(1) автомат К находится в состоянии S1;

(2) автомат читает первый (слева) символ слова х, либо он читает

(пустой) признак конца слова (символ #).

В этом втором варианте автомат применяется к пустому слову L.

Говорят, что автомат К д о п у с к а е т слово

(или, иначе, ч и т а е т слово), если в результате выполнения

его команд он приходит в финальное состояние когда слово

прочитано до конца (читается правый ограничитиель).

Pабота конечного автомата заключается в изменении состояний

в соответствии с его командами, или, иначе в смене конфигураций.

Последовательность конфигураций при работе автомата называется

п р о т о к о л о м.

Каждый автомат Мура реализует некоторый предикат на

множестве входных слов (допускает он слово или нет).

Каждый автомат Мили реализует (однозначную или

неоднозначную ) функцию с областью определения на множестве

Замечание. Автомат не допускает слова в двух

случаях: (1) нет подходящей команды, (2) слово прочитано,

а автомат не находится в финальном состоянии.

П р и м е р 1. Автомат К1 без выхода с командами

читает слово х = abab.

конфигурация подходящая команда

S1 3 — нормальный останов

Таким образом, К1 допускает х=abab

Тот же автомат не допускает слова x=aba (составьте протокол).

П р и м е р 2. Автомат Мили К2 подавляет левые нули.

Команды автомата К2:

Пусть К2 означает функцию, реализуемую конечным автоматом К2.

K2 (0001011) = 1011

K2 (1.2) = ? — нет подходящей команды.

Конечные автоматы удобно изображать на графах с помеченными

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

S1 a → S2 x, где a — входной символ, а х — выходное слово, изображаются на дугах в виде пары a: x через двоеточие.

Говорят, что дуги в зависимости от того, как они помечены,

есть дуги разного т и п а.

Автомат Мили: подавление левых незначащих нулей в двоичных дробях

У п р а ж н е н и е. Автомат сверачивает все слова в одну букву,

а все числа — в другую. Алфавит . Нарисуйте граф.

Конечные автоматы применяются как распознаватели, как кодирующие устройства и как преобразователи (препроцессоры)

для лексической (словесной) подготовки алгоритмов анализа и преобразования текстов.

Синтаксическому анализу и трансляции, как правило,

предшествует так называемая лексическая подготовка.

В зависимости от схемы анализа и задач трансляции в задачу лексической подготовки входит

(1) Удаление незначащих пробелов.

(2) Обнаружение ошибочных пробелов. Общее правило: слова разделя-

ются знаками либо пробелами (лишние пробелы незначимы).

(3) Перекодировка всех служебных слов в одну букву.

(4) Перекодировка всех слов программиста в одну букву.

(5) Перекодировка всех чисел в одну букву.

(6) Pасстановка маркеров для операндов при трансляции.

(7) Переобозначения символов и слов

Автоматные языки называют кратко А-языками или языками «регулярных выражений».

Определение 1. Множество слов, допускаемых конечным

автоматом, называется а в т о м а т н ы м языком или А — языком.

П р и м е р ы А-языков:

L4 = * L5 = a*b* L6 = a* È b*

У п р а ж н е н и е: построить для этих языков конечные автоматы.

Определение 2. Два конечных автомата называются

э к в и в а л е н т н ы м и, если они допускают один и тот же язык.

Операции над А-языками

Докажем, что объединение А-языков есть А-язык.

Лемма 1. Для любого конечного автомата можно построить

эквивалентный автомат, в графе которого в начальном состоянии

присyтствyют только выходящие дyги.

Доказательство. Введем новое начальное состояние S’1, и

дyги всех типов, выходящие из S1, направим также из S’1

в соответствующие вершины. Все входящие дyги оставим

без изменения. Все петли вида S1 а ® S1 b заменим на дyги вида

S1’а ® S1 b. Требуемый автомат построен. Лемма доказана. ÿ

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

Теорема 1 . Объединение автоматных языков есть А-язык.

Доказательство. Пусть L1 и L2 — два автоматных языка,

а G1 и G2 — графы читающих их автоматов Мура. Согласно

лемме 1, не ограничивая общности, можно считать, что начальные

вершины в G1 и G2 не имеют входящих дуг. Добавим новую

вершину, которую совместим с начальными вершинами обоих графов.

Чтение слов в этом новом графе проходит либо по дугам первого автомата, либо по дугам второго, т. е. либо по графу G1, либо по дугам G2. При этом читаются слова L1 È L2.

Теорема доказана. ÿ

Теорема 2. Произведение А-языков есть А-язык.

Доказательство. Построим новый конечный автомат, допyс-

кающий произведение языков L1 и L2. Не ограничивая общности,

можно считать, что у первого автомата заключительное состояние

только одно. Граф второго автомата преобразуем по лемме 1 так,

чтобы в начальную вершину не входила ни одна дуга. Затем

совместим ее с заключительной вершиной первого графа.

В полученном графе читается сначала слово первого языка, а затем

слово второго. Получаем автомат, допускающий язык L1L2. ÿ

У п р а ж н е н и е: построить граф автомата для

произведения языков (a, b*)(b, c*).

Теорема 3. Итерация Клини А-языка есть А-язык.

Доказательство. Пусть L — автоматный язык, а G — его граф.

Все дyги, ведyщие в заключительные вершины G, направим в начальное состояние этого графа. Добавим свободнyю дyгy, выходящую из начальной вершины. Граф автомата, допускающего язык L* , построен. ÿ

У п р а ж н е н и е: построить конечный автомат для L=* .

Из доказанных утверждений следует известная теорема:

Первая теорема Клини (Теорема 4).

Класс А-языков замкнут относительно операций объединения, умножения и итерации Клини.

Определение. Формулой Клини называется конечное выражение, составленное из знаков действия +, умножения (по умолчанию) * и скобок и символов в качестве операндов, включая символы пустого слова

и пустого языка.

П р и м е р: (a+b)c ab* (a+b+L)* а*(b+cd)* − формулы Клини

Следствие 1. Любая формула Клини представляет некоторый

Вторая теорема Клини (Теорема 5). Любой А-язык может быть представлен в виде формулы Клини.

Доказательство. Заметим, что

1) каждое слово есть произведение (конкатенация) символов и,

значит, представляется в виде формулы Клини;

2) каждый конечный язык есть объединение слов и, значит, он

представляется в виде формулы Клини; Будем доказывать теорему

по индукции по числу незаключительных дуг автомата n.

При n=0 дуги только заключительные; если автомат допускает

какое-либо слово, то это пустое слово L (или язык пуст, L=O).

При n=1 автомат допускает либо О, либо L, либо один

единственный символ ‘а’ (тот, которым помечена дуга), либо a*.

Пусть любой автомат с графом G имеет m незаключительных дуг, где m ≤ n представим формулой Клини. Рассмотрим автомат,


который читает язык L и граф которого содержит n+1

незаключительную дугу, а именно, дугу Si a ® Sj.

Заметим, что множество слов, читаемых в этом графе, начиная

с S1 и кончая Si, есть А-язык, допускаемый автоматом,

в графе которого не больше чем n незаключительных дуг. Значит,

этот язык (обозначим его L(1i) представим в виде формулы Клини.

Аналогично, язык из слов, читаемых при движении от Sj к одной

из заключительных вершин без посещения Si и Sj есть А-язык и

он представим в виде формулы Клини (обозначим его L(j) ).

Далее, по предположению индукции, представимы в виде формул Клини языки L(1), L(i) , L(j) порождаемые без прохода по дуге (i, j ) при движении при движении из вершин S1, Si и Sj, а также языки L(1i) и

L(ji), порождаемые при движении из S1 в вершину Si и из Sj в Si

без прохода по дуге (i, j). Легко видеть, что

L = L(1) + L(1i) [a L(ji)]*(L(i)+ a L(j)) .

Это – формула Клини. Значит, предположение индукции верно

также для n=n+1. Теорема доказана. ÿ

Детерминированные конечные автоматы

Определение. Конечный автомат K называется

д е т е р м и н и р о в а н н ы м, если в списке его команд нет ни одной пары команд с совпадающими левыми частями.

В противном случае автомат называется недетерминированным.

Детерминированный конечный автомат представляет некоторый алгоритм обработки входного слова. Недетерминированный автомат представляет множество алгоритмов.

Теорема 6 (о детерминизации). Для каждого конечногоj автомата можно построить эквивалентный детерминированный конечный автомат.

Доказательство проводится по индукции по числу

незаключительных продукций. Пусть К = (A, S, SF, P) — исходный,

возможно недетерминированный конечный автомат, заданный графом G.

Построим новый конечный автомат K’ = (A’, S’, S’F, P’),

где A – тот же алфавит, S – множество всех подмножеств S,

а P – множество дуг, проведенных следующим образом.

Пусть f: (S, A) ® S функция переходов автомата К.

Построим функцию переходов нового автомата К’

g: (S’,A)® S так, что для каждого символа a из A для каждого состояния S’i автомата К’

где объединение включает все элементы Sj, содержащиеся в S’i.

Пусть в новом автомате заключительными будут все состояния S’i,

которые содержат хотя бы одно заключительное состояние автомата К:

S’F = È(S’i: S’i Ç SF не пусто).

Построенный автомат К’ — детерминированный, так как функция

g однозначна. По построению любое слово, которое допускает К допускается также автоматом К’. Наоборот, если слово

допускается автоматом К’, значит, найдется путь на графе К по

которому читается это слово и свободный выход в конце слова.

Значит, оба автомата допускают один и тот же язык. Теорема доказана. ÿ

Замечание. Число состояний построенного детерминированного автомата не более 2 в степени n, где n — число состояний исходного

автомата. Говорят, что детерминизация конечных автоматов имеет «экспоненциальную сложность».

Следующие теоремы опираются на свойства детерминированных

Теорема 7. Дополнение к автоматному языку есть автоматный язык.

Доказательство. Пусть L — автоматный язык в алфавите A,

L = L(A). Для L можно построить допускающий L конечный

автомат. Детерминируем этот автомат по предыдущей теореме. Пусть детерминированный конечный автомат К допускает L.

Преобразуем граф этого автомата.

Этап 1. Все заключительные состояния сделаем незаключительными (сотрем свободные стрелки), а все незаключительные состояния сделаем заключительными (подрисуем свободные стрелки).

Этап 2. Введем новое состояние R, и пусть из R выходят

петли всех типов и свободная стрелка. Тогда исходя из R

можно прочесть любое слово из A* .

Этап 3. Из каждой вершины графа направим дуги всех недостающих типов в R. Тогда из каждой вершины на графе будут исходить дуги всех типов.

Построенный граф изображает автомат K’, допускающий язык,

дополнительный к L. Докажем это. Пусть слово х допускается

автоматом K. В силу его детерминированности существует

единственный путь на графе, по которому читается х, а также единственный путь, по которому читается х на графе K’.

. Но последняя вершина, заключительная в K не есть заключитель-

ная в К’. Значит, х не допускается автоматом К . Пусть, напротив, слово х не допускается К. Значит, оно будет читаться не до конца

или после конца слова не будет выхода. В первом случае недостающая

в К стрелка пойдет в К’ в вершину R, где читаются любые

продолжения и, значит, К допускает слово х. Во втором случае последняя вершина в К будет незаключительной, и значит, она

будет заключительной в К’. Таким образом, слово x в обоих

случаях будет допускаться автоматом К.

Эквивалентность К и К’ доказана. ÿ

П р и м е р. Пусть язык L= a*b допускается автоматом, граф

которого имеет вид

После первых двух этапов преобразований получаем граф:

c новой вершиной R и дугами из вершины 2 в R типа a и b.

Вершины 1 и R являются заключительными. Постройте граф.

Видно, что в этом графе допускается язык a* + a*b(a+b)(a+b)* , дополнительный к L= a*b.

Теорема 8. Пересечение А-языков есть А-язык.

Доказательство. Пусть L1 и L2 — А-языки.

По формуле двойственности для множеств L1 Ç L2 = \(\L1È\L2).

По предыдущей теореме \L1 и \L2 ─ А-языки, согласно первой теореме

Клини их объединение есть А-язык и дополнение к нему – тоже А-язык.

Замечание 1. Существует алгоритм, который по виду

любых двух конечных автоматов определяет эквивалентны они или нет.

Действительно, пусть конечные автоматы К1 и К2 допускают

А-языки L1 и L2. Эквивалентность автоматов есть равенcтво L1=L2.

Но эти множества равны тогда и только тогда, когда

одновременно L3 = \L1Ç L2 = O и L4 = L1Ç\L2 = O.

По двум предыдущим теоремам дополнения к L1 и L2 cуть A-языки и

L3 и L4 суть A-языки. А-язык пуст тогда и только тогда, когда

в графе автомата из начальной вершины нет пути, приводящего к

свободной стрелке. Это легко проверяется по графу.

Определение. Две вершины в графе автомата называются эквива — лентными, если исходя из них читаются совпадающие множества слов (языки).

Замечание 2. Объединение эквивалентных вершин на графе автомата порождает новый эквивалентный автомат с меньшим числом вершин.

Построение эквивалентных автоматов меньшей сложности

называют минимизацией автомата. Метод объединения эквивалентных

вершин позволяет построить м и н и м а л ь н ы й эквивалентный конечный автомат. При любой функции сложности, располагая алгоритмом проверки эквивалентности, можно построить алгоритм минимизации относительно этой функции эквивалентности.

Говорят, что в конечных автоматах нет неразрешимых проблем.

Илон Маск рекомендует:  Что такое код registerbgifont

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

Теорема 9. Язык , где n=0,1,2. не есть А-язык.

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

построить допускающий его конечный автомат. По теореме

о детерминизации существует эквивалентный ему детерминированный

конечный автомат К . Возьмем n больше, чем число состояний К.

Читая bn, автомат должен будет пройти некоторые состояния К

дважды. Пусть это будет состояние Sx. Значит, на графе

автомата из Sx есть непустой цикл. Пусть в этом цикле читается

слово w = bm длины m > 0. Тогда, значит, автомат К

допускает слова an bn, anb n+l, anbn+2.

То есть, К допускает другой язык. Установленное

противоречие доказывает теорему. ÿ

Замечание. В этой теореме символы а и b могут

интерпретироваться как открывающие и закрывающие скобки.

Конечные автоматы не позволяют вести счет числа парных

скобок (в силу конечности их памяти, ограниченной числом

Говорят, что конечные автоматы «не умеют считать».

У п р а ж н е н и я

1. Напишите формулу Клини для языка, который допускается

1/ S1 a ® S2; S1 ® ; S2 b ® S1 ; S2 ® ;

2/ S1 a ® S2; S1 ® ; S2 a ® S2; S2 b ® S2; S2 ® ;

3/ S1 a® S2; S1 b® S1; S2 a® S2; S2 ® ;

4/ S1 a ® S1; S1 b ® S1; S1 ® ; S1 c ® S2; S2 ® ;

5/ S1 b ® S1; S1 a ® S2; S2 b ® S2; S2 a ® S2; S2 ®

6/ S1 a ® S2; S2 a ® S3; S2 ® ; S3 b ® S2;

2. Нарисуйте графы автоматов, которые допускают языки

1/ a*(a+b) 2/ a(b+c)* 3/ a*+b*

3. Выполните построение по теореме и нарисуйте граф автомата,

который допускает язык дополнительный к

1/ ab*a 2/ a*bb 3/ a(a+b)* 4/ a*(a+b) 5/ (ab)* 6/ a*+b

4. Напишите формулу Клини по этим автоматам.

5. Выполните построение по теореме и детерминируйте автоматы

1/ S1 a ® S3; S1 a ® S2; S3 ® ; S2 b ® S2; S2 ® ;

2/ S1 a® S1; S1 ® ; S1 a ® S2; S2 b ® S2; S2 ®;

3/ S1 a ® S1; S1 a ® S2; S1 b ® S1; S2 ® ;

4/ S1 a ® S1; S1 b ® S1; S1® ; S1 a ® S2; S2® ;


5/ S1 a ® S2; S1 b ® S2; S1 b ® S1; S2 ® ;

6/ S1 a ® S2; S1 ® ; S2 b ® S2; S2 b ® S1 ;

2. КОНТЕКСТНО-СВОБОДНЫЕ (КС-) ГРАММАТИКИ И ЯЗЫКИ

Контекстно-свободные языки широко используются как

формальные модели языков программирования и естественных языков.

Для описания синтаксиса языков программирования обычно применяют

следующий специальный метаязык.

Бэкусовы нормальные формы (БНФ)

Голландский теоретик Вайнгартен, автор первого алгоритмического языка Алгол-60, использовал так называемые формы Бэкyса-Hаyра (Backus-Naur forms). Это – простой метаязык для описания синтакси-

са формальных языков. Символы БНФ делятся на объектные и (символы языка) и вспомогательные (синтаксические).

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

Знак ::= означает «есть по определению»,

а знак | означает «или» .

БНФ есть набор разрешенных подстановок

Для определения понятий, представленных цепочками символов

произвольной длины, используются определения этих понятий через них самих (“рекурсивный определения”).

Например: определение слова:

Здесь второе определение р е к у р с и в н о : повторяя вторую

подстановку много раз можно в ы в е с т и слова в алфавите

из любого количества букв. Например, выведем слово bca:

Примеры идентификаторов: a, ab, a1, bba, a3b2, b111

Определение целых чисел:

Синтаксис десятичных чисел:

Такой синтаксис имеет, например, фраза:

УМНЫЙ ПЕТЯ БЕГАЕТ БЫСТPО

Для построения арифметических выражений вводится понятие «терм». Термом называется либо отдельная переменная, либо выражение в скобках.

Синтаксис простейших арифметических выражений:

Описание языка при помощи БHФ приспособлено для понимания

смысла человеком, БНФ используют в руководствах по описанию языков,

и при проектировании новых языков. Для формального анализа и обработки на компьютере более удобен аппарат сжатого описания в виде формальных

Определение 1. Контекстно-свободной или КС-грамматикой называется четверка G=(@, N, T, P), где

N – конечное множество нетерминальных символов языка.

пусть элементы множества N обозначаются прописными бyквами;

T – конечное множество терминальных символов. Пересечение множеств N и T пусто. Элементы множества T будем обозначать строчными буквами,

P – конечное множество продукций вида A® u,

где А — нетерминал, а u в левой части продукции — слово из

символов объединенного алфавита, u из (N ÈT)*.

П р и м е р ы КС-грамматик:

4/ @ ® aAb A ® cA A ® с

5/ @ ® A A® B A® a B ® bB B® b

Определение 2. Последовательное применение продукций

грамматики называется выводом. Вывод в грамматике считается

законченным, если получилось слово только из терминальных символов.

Определение 3. Множество L слов, выводимых в G из

аксиомы @, называется языком, порожденным грамматикой G. Этот

факт будем записывать в виде @ ==> L или G ==> L.

Контекстно-свободным языком называется язык, порожденный

П р и м е р : КС-языки, порождаемые КС-грамматиками 1-5 из

x>, где х — любые слова из символов ,

а волна означает обращение (запись цепочки справа налево).

Теорема 1 (о свойствах КС-языков).

1. Объединение КС-языков есть КС-язык.

2. Произведение КС-языков есть КС-язык.

3. Итерация Клини КС-языка есть КС-язык.

Доказательство. Пусть L1 и L2 — два КС-языка, а G1= (@1, N1, T1, P1) и G2= (@2, N2, T2, P2) — их КС-грамматики.

Не ограничивая общности, будем считать, что N1 и N2 не

Построим новую грамматику G= (@, N, T, P) следующим образом:

Очевидно, что @ ==> L1ÈL2 . Утверждение 1 доказано.

Пусть, как и выше, G1 и G2 суть КС-грамматики и N1ÇN2 = O.

Построим новую грамматику:

Очевидно, что @ ==> @1 @2 ==> L1L2. Утверждение 2 доказано.

По грамматике G1 построим грамматику

Очевидно, что @ ==> @1* ==> L1*.

Теорема доказана. ÿ

не описывается никакой КС-грамматикой (обоснование см. ниже).

Замечание 2. Существуют такие КС-языки, пересечение

которых не является КС-языком.

L1= , n, m ³ 0 и L2= , n, m ³ 0

(докажите) cуть КС-языки. Их пересечение L1ÇL2 = L.

Определение 4. Любая цепочка символов, выводимая

из аксиомы называется с е н т е н ц и а л ь н о й ф о р м о й.

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

являются сентенциальными формами.

Важнейший вопрос: существует ли (общий для всех грамма-

тик и слов) алгоритм, который распознает выводимость слова в

Распознаваемые множества по традиции называются рекурсивными.

Установим свойство рекурсивности КС-языков. В главе 1 было доказано,

что если все продукции не укорачивают сентенциальных форм,

то такой алгоритм существует.

Определение 5. Продукция КС-грамматики, правая часть которой

не есть пустое слово, называется н е у к о р а ч и в а ю щ е й.

Грамматика, не содержащая ни одной укорачивающей продукции назы-

вается неукорачивающей грамматикой.

Теорема 2. Любая неукорачивающая грамматика порождает рекурсивный (т. е. распознаваемый) язык.

Доказательство. Опишем алгоритм распознавания. Пусть дано

слово х длины m. Будем порождать сентенциальные формы сверху

вниз начиная с аксиомы, выписывая только те из них, длина

которых не больше m. Число таких форм конечно, оно не больше, чем (|N|+|T|)m (здесь знак абсолютной величины означает число элементов в множестве). Выпишем свержу вниз исходя из аксиомы все такие сентенциальные формы. Остается проверить, есть в этом

списке х или нет. □

Выводимость пустого слова проверяется отдельно:

Теорема 3. Существует алгоритм, который за конечное

число шагов проверяет, выводимо в КС-грамматике пустое слово или нет.

Доказательство. Назовем исчезающими нетерминалами такие

нетерминалы, из которых можно вывести (за конечное число

шагов) пустое слово. Число шагов для вывода пустого слова

назовем п о р я д к о м исчезающего нетерминала.

Нетерминалы первого порядка, переходящие в пустое слово

за один шаг, выписываются по продукциям непосредственно.

Все нетерминалы (n+1) порядка можно получить из продукций

A ® u, где u — слово, составленное лишь из нетерминалов

порядков 1, . ,n. Увеличивая n, мы получим неубывающие

множества исчезающих нетерминалов, мощность которых ограничена

сверху общим числом нетерминалов. Таким образом, за конечное

число шагов мы получим множество всех исчезающих нетерминалов.

Остается проверить, есть среди них аксиома или нет. ÿ

Замечание 3. Для каждой КС-грамматики G, порождающей

язык L, можно построить неyкорачивающyю грамматикy G1, которая

порождает язык L — L (без пустого слова).

Для этого, очевидно, надо заменить все исчезающие нетерминалы на пустое слово во всех продукциях во всех комбинациях, а затем вычеркнуть укорачивающие продукции.

Следствие (рекурсивность КС-языков).

Существует такой общий алгоритм, который по видy любой

КС-грамматики для любого слова выясняет выводимость этого слова

в этой грамматике (за конечное число шагов).

Докажем, что пустота и конечность КС-языков оказываются распознаваемыми свойствами.

Теорема 4. Сyществyет алгоритм распознавания пyстоты КС-языков (за конечное число шагов).

Доказательство этой теоремы аналогично доказательству

теоремы 2. Сначала выписываются все нетерминалы, из которых

вывод заканчивается за один шаг, они называются надтерминалами

первого порядка. Затем выписываются все нетерминалы, из которых

за один шаг выводятся сентенциальные формы, состоящие только

из терминалов и надтерминальных символов первого порядка.

Затем выписываются надтерминальные символы высших порядков.

Но число нетерминалов конечно. Ясно, что за конечное число шагов таким образом можно выписать множество всех нетерминалов, из которых можно закончить вывод. Остается проверить, есть среди них аксиома или нет.

Во втором случае, очевидно, язык пуст. ÿ

Определение 6. Нетерминал в грамматике называется

н е д о с т и ж и м ы м, если его нельзя получить из аксиомы.

Нетерминал в грамматике называется н и л ь п о т е н т н ы м,

если из него нельзя получить терминальную цепочку.


Определение 7. КС-грамматика называется приведенной

если она не содержит недостижимых и нильпотентных нетерминалов.

Теорема 5. Для любой КС-грамматики G можно построить

эквивалентную приведенную КС-грамматику (за конечное число шагов).

Доказательство. Все достижимые нетерминалы выписываются по

продукциям грамматики непосредственно, а значит, выписываются

и все недостижимые. Возьмем какой-нибудь нетерминал А в качестве

аксиомы. Получим другую КС-грамматику, которая порождает КС-язык,

и н д у ц и р о в а н н ы й этим нетерминалом. Этот индуцированный

язык пуст тогда и только тогда, когда А в G — есть нильпотентный символ. Теорема 2 позволяет проверить это свойство за конечное число шагов.

Таким образом, мы можем выписать все недостижимые и

нильпотентные нетерминалы. Вычеркивая все содержащие их продукции,

получаем эквивалентную приведенную грамматику. ÿ

Говорят, что в КС-грамматике есть нетривиальный цикл выводов, если можно указать такой нетерминал А, что из А можно вывести uAv,

Теорема 6. Сyществyет алгоритм распознавания бесконечности

КС-языков (за конечное число шагов).

Доказательство. Заметим, что достаточно рассмотреть только

приведенные неукорачивающие грамматики. Замечаем, что

приведенная КС-грамматика порождает бесконечный язык тогда и

только тогда, когда в этой грамматике есть хотя бы один нетривиальный цикл выводов. Действительно, пусть А ==> uAv — цикл выводов. Из u и v в приведенной неукорачивающей грамматике всегда можно закончить вывод так, что А ==> xAy, где х и y — слова из только терминальных символов, причем |x|+|y| > 0. В приведенной КС-грамматике нетерминал А может быть выведен из аксиомы. Значит, могут быть выведены слова, содержащие xn A yn при любом n, т. е. бесконечное множество слов языка.

Обратно: пусть теперь в приведенной неукорачивающей

КС-грамматике нет ни одного цикла вывода. Будем выполнять все выводы, начиная с аксиомы, разворачивая все нетерминалы за один шаг

по дереву вывода. Применение каждой продукции может удлинить

сентенциальную форму на некоторое ограниченное число символов,

но из-за отсутствия циклов выводов ни одна продукция не может быть

применена дважды. Число продукций ограничено. Значит, может

получиться только конечное множество деревьев вывода и только

конечное множество слов. Теорема доказана. ÿ

Выводы в КС-грамматиках удобно изображать в виде

д е р е в ь е в в ы в о д а. Применение каждой продукции изображается разветвлением. Нетерминалы обычно рисуются в кружочках.

1. Грамматика @ ® *****@***@ ® cc

(1) однозначно устанавливают порядок развертки слова из аксиомы,

(2) однозначно определяют порядок свертки слова и

(3) представляют решение задачи определения выводимости слова

Определение. Синтаксическим анализом слова х

в грамматике G называется определение дерева вывода х в G.

Замечание 4. Теоремы о рекурсивности КС-языков

устанавливают существование алгоритма, который находит

дерево вывода слова в грамматике.

Замечание 5. Каждую КС-грамматику можно представить как систему уравнений относительно языковых переменных.

Действительно, ограничимся неукорачивающими грамматиками.

Каждый нетерминал А в грамматике, очевидно, определет

некоторый «индуцированный» КС-язык L(A) из слов выводимых

из A. Будем пользоваться знаком плюс для обозначения

объединения языков, а знак умножения (конкатенации) будем опускать.

Тогда, например, КС-грамматика

@ ® A@ @ ® L A ® BA A ® C A ® aa B ®@B B® bb

может быть представлена в виде системы уравнений:

L(A) = L(B)L(A) + L(C) + aa

Такую систему можно решать итеративно:

итерация 0: L0(@)=c L0(A)=aa L0(B)=bb L0(C)=0,

итерация 1: L1(@)=aa+c L1(A)=bbaa+aa L1(B)=cbb L1(C)=O, и так далее.

Определение 8. КС-грамматика называется нормальной,

если для всех ее прoдукций А ® u длина u не больше двух.

Замечание 6. Для каждой КС-грамматики можно построить

эквивалентную нормальную КС-грамматику.

Действительно, вводя новые нетерминалы можно расписать,

например, продукцию A ® aABbA в виде

A ®aC C ® AD D ® BE E ® bA.

Теорема 7 (Эрли) . Можно построить такой алгоритм, который по виду произвольной КС-грамматики G и любого слова х устанавливает выводимость G ==> x не более, чем за с|x|3 шагов, где с зависит

только от грамматики.

Доказательством является построение алгоритма анализа

(однозначных и неоднозгачных) КС-яыков за число шагов,

пропорциональное кубу длины слова х. Опишем идею построения такого алгоритма (подробнее см. в [7] и [10] ). Этот алгоритм строится путем развертки сверху вниз с сохранением всех возникающих промежуточных деревьев и отбрасыванием на каждом шагу тех, которые уже не могут привести к выводу х. Число таких деревьев не превосходит |x|2 и значит, число шагов до получения х не превосходит с|x|3.

Однако, такой кубически трудоемкий анализ является практически слишком трудоемким. Принято пользоваться только такими грамматиками: которые допускают линейный анализ, то есть за число шагов c|x|

АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ

Заметим, что язык L=, n=1,2. не распознается

никаким конечным автоматом, так как нужно запоминать an,

n=1,2. т. е. нужна бесконечная память. Возникает идея:

cкладывать символы в очередь, в «стек».

Определение 9. Стек — стопка (например, книг) есть

организация памяти с дисциплиной обслуживания

LIFO: last in — first out.

Определение 10. Автоматом с магазинной памятью или

МП-автоматом называется конечный автомат с магазинной памятью

(со стеком) неограниченного объема, в который можно заносить

цепочки символов и считывать с извлечением из стека.

в х о д н о е с л о в о # # # # # # # # # # # # # # # # #

Работа МП-автомата разбивается на такты.

Верхняя лента входная, она движется справа налево на одну ячейку

за такт. Нижняя лента – магазин или стек называется иначе “рабочей лентой”. Она может двигаться в обе стороны, но ее правая часть недоступна для чтения и записи. Чтобы прочесть предыдущую запись в ней надо выгнуть все последующие. За один такт со входной ленты читается ровно один символ, а в стек записывается символ или слово (возможно, пустое), При чтении рабочая лента сдвигается на одну ячеку вправо, что соответ-ствует выниманию символа из стека.

Команды МП-автомата — это расширение команд конечного

автомата, в которые добавлено занесение в стек и извлечение из стека

Основной формат команд

a Si b ® x Sj где Si – состояние УУ автомата,

a – символ, вынимаемый из стека,

b – читаемый символ со входной ленты

Sj – новое состояние,

x – слово, которое заносится в стек.

Укороченные варианты команд:

МП-автомат может «закрыть глаз» на одну из лент и не обращаться к ней,

Здесь опущенные поля справа и слева вокруг Si (Sj) означают, что

символы из входной ленты стека и, соответственно, из стека не читаются

и не извлекаются из стека, при этом соответствующие ленты неподвижны.

Определение 11. Состояние МП-автомата SF называется заключительным. Говорят, что МП-автомат д о п у с к а е т слово, если в результате его прочтения и выполнения команд он оказывается в состоянии SF. Такая ситуация называется “нормальный останов”. В случае, если не находится подходящей команды или после прочтения слова автомат оказы-вается в другом состоянии, говорят, что МП-автомат н е д о п у с к а е т этого слова.

МП-автоматы удобны для распознавания КС-языков.

Рассмотрим один пример.

П р и м е р 1. Язык симметричных цепочек с буквой «с»

xcx>, x принадлежит *

(здесь и ниже волна означает обращение, т. е. запись цепочки

справа налево) Распознаватель этого языка может иметь вид

1. S1 a ® a S1 — перенос в стек

3. S1 c ® S2 — состояние сравнения

5. b S2 b ® S2 — сравнение символов

Совокупное состояние УУ и лент МП-автомата называется

к о н ф и г у р а ц и е й МП-автомата.

Конфигурации удобно записывать, вписывая состояние между

содержимым стека и непрочитанной части входной ленты. Получаем

удобную запись протокола.

П р и м е р : cвертка слова aabcbaa (прокрутка) на автомате

Смена конфигураций: команды

#S2# — нормальный останов 6

П р и м е р 2. Pаспознавание скобочных выражений

Здесь в стеке накапливаются открывающие скобки для сравнения их

числа с числом закрывающих скобок.

П р и м е р 3: распознавание произведений вида (a(aaf())(a)f(),

где функция f() не имеет аргументов.

Теорема 8. Класс языков, допускаемых (не обязательно

детерминированными) МП-автоматами, совпадает с классом КС-языков.

Доказательство. Построим сначала МП-автомат по произвольной

Пусть в этом автомате выражения [A] для различных нетерминалов A из алфавита N означают его “синтаксические состояния”.

1. S1 ® @S2 ничего не читаетcя, но аксиома заносится в стек.

2. АS2 ® [A] для всех А из N.

Т. е. если в стеке – нетерминал,

то независимо от содержания входной ленты автомат

переходит в “синтаксическое состояние” [A].

uS1 для всех продукций грамматики G вида G ® u.

4. аS2a ® S2 для всех терминалов a из T.

5. #S2# ® SF если стек пуст и слово прочитано, то нормальный останов.


Нетрудно убедиться, что этот автомат выполняет работу по развертке

слов языка из аксиомы. Построенный МП-автомат допускает язык G® L.

В одну сторону теорема доказана.

Пусть теперь дан МП-автомат, построим по нему КС-грамма-

тику. Не ограничивая общности, рассмотрим только автомат с

полными форматами команд. Заметим: что каждую команду записи

слова в стек a Si b ® x Sj можно переписать в виде группы команд

с посимвольным занесением слова х в стек, и можно ограничиться

рассмотрением команд вида ai Sj b ® ak Sm, где ai и b

отдельные символы, i=1, . ,|S|. Построим грамматику G=(@, N, T, P)

с аксиомой @, алфавитом символов N вида Aij = (ai Sj) и с алфавитом T всех символов, которые пишет и читает МП-автомат. Перепишем команды МП-автомата в виде продукций:

ai Sj b® SF @ ® Aij b S1 b ® ak Sm

ai Sj b® ak Sm Akm ® Aij b Akm ® b

Видно: что в построенной грамматике выводы отслеживают

выполнение команд МП-автомата в обратном порядке.

КС-грамматика языка L построена. ÿ

Однако, МП-автомат, построенный по теореме 8 может иметь

команды с совпадающими левыми частями и будет, вообще говоря,

П р и м е р. Язык L=an cc bn где n=0,1,2. Грамматика:

Слово w = aacсbb

МП-анализ по теореме 8:

конфигурация группа команд вариант

Возможность выбора вариантов делает автомат недетерминированным.

1) Доказанная теорема гарантирует построение только недетер-

2) МП-автомат может решать задачу отыскания нужного пути

развертки. Перебор вариантов удлиняет распознавание.

3) Существует кубический (по длине слова) алгоритм

отыскания путей развертки произвольных слов.

Замечание. Детерминизация МП-автоматов в общем

случае не удается, так как наталкивается на алгоритмически

неразрешимые проблемы (см. ниже в разделе 5).

x цепочку x, записанную справа налево.

Теорема 9. Существуют КС-языки, например, язык L=

где х из * (симметричных слов без центра),

которые не допускаются никаким детерминированным МП-автоматом.

Доказательство. Предположим противное: пусть детерминированный МП-автомат K допускает язык L. Слова вида w= x

y, очевидно, тоже должны допускаться автоматом K. Выберем длину слов y больше числа состояний автомата. После прочтения слова x=y

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

yy надо знать по крайней мере его длину. Но автомат K не располагает для этого достаточной памятью (числом состояний). Теорема доказана. ÿ

Определение 12 (Шейлы Грейбах). КС-язык называется

детерминированным, если он допускается некоторым детерминированным МП-автоматом.

Для любой неукорачивающей КС-грамматики, очевидно,

можно построить эквивалентную «удлиняющую» КС-грамматику,

путем всевозможных подстановок В вместо А для продукций вида

А®B в другие продукции. В удлинняющей КС-грамматике на каждом шагу свертки исчезает хотя бы один символ и вся свертка требует числа шагов не больше длины слова. Построенный по ней детерминированный

МП-анализатор будет работать за время, пропорциональное длине входного слова. Возникает практическая задача построения детерминированных (беспереборных) МП-автоматов.

Говорят, что МП-автоматы выполняют синтаксический анализ

типа «перенос-свертка». Будем искать детерминированные

алгоритмы типа «перенос-свертка» . Теорема Эрли обеспечивает трудоемкость синтаксического анализа пропорционально кубу длины входного слова. Для практических приложений, однако, это

неприемлемо. С целью ускорения алгоритмов синтаксического анализа приходится ограничивать класс КС-грамматик и пользоваться только такими КС-грамматиками, которые допускают синтаксический анализ

за время, пропорциональное длине слова n. Анализ, который

для слова х длины m требует не более, чем cm операций, где с

от х не зависит (а зависит только от грамматики), называется

линейным или беспереборным.

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

Но дерево вывода, обычно aрriori неизвестно. Заметим, что проанализировать слово за время меньше чем c*n невозможно: ведь слово надо прочесть хотя бы один раз до конца.

Рассмотрим механизм свертки сентенциальных форм в МП-автоматах.

Определение. О с н о в о й сентенциальной формы

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

которая подлежит сверке согласно дереву вывода.

Грамматика @® AB A® a B®bB B ®b .

Здесь имеются основы четырех видов: AB, a, bB, b

Пусть дано слово x = abb.

На первом шагу свертки видны две основы (a и правое b).

AbB (слева направо) aB (cправа налево)

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

свертки умеем находить основу (левую, правую или какую-нибудь другую).

У п р а ж н е н и я

1. Напишите КС-грамматику G для языков

1/ L = ((ab)n bm cn+1)

5/ L – язык из символов a, b, c c симметричными фразами

x>, где x любые слова из символов .

2. Опишите с помощью БНФ грааматику одного из языков,

приведенных в приложении 2.

3. Введите обозначения для нетерминалов и переведите БНФ

в КС-грамматику G.

4. Постройте дерево вывода предложенной вам типовой фразы

и выпишите по нему 10 отношений простого предшествования

Синтаксический анализ

Синтаксический анализ (парсинг) — преобразование последовательности символов на естественном или искусственном языке в соответствии с формальной грамматикой. Англоязычный термин parsing образован от латинского pars ōrātiōnis, означающего «часть речи».

Найдите научные статьи по этой теме в трудах российских NLP-конференций.

Содержание

Контекстно-свободные грамматики

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

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

КС-язык

Дерево вывода

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

Алгоритм построения дерева вывода грамматики выглядит следующим образом.

Порядок нумерации ярусов дерева: корень дерева располагается в нулевом ярусе. Вершины дерева, смежные с корнем образуют первый ярус и т.д. Дуги, выходящие из вершин i <\displaystyle i>-го яруса, ведут к вершинам i + 1 <\displaystyle i+1>яруса.

Высотой дерева называется максимальная длина пути от корня дерева к листу (т.е. номер последнего яруса).

Применение контекстно-свободных грамматик

Контекстно-свободные грамматики хорошо зарекомендовали себя в задачах разбора многих западноевропейских языков, таких как английский.

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

Машинный разбор предложения с использованием контекстно-свободных грамматик реализуется при помощи алгоритма Эрли или алгоритма Кока — Янгера — Касами.

Примеры КС-грамматик

  • Язык Дика (последовательность правильных расстановок скобок)

Язык Дика описывается грамматикой следующего вида:

  • Язык арифметических выражений

Пример грамматики, генерирующей строки, представляющие арифметические выражения со следующими операциями: + , − , ∗ , / <\displaystyle +,-,*,/>и числами как операндами.

  • Лямбда-исчисление [1] .
  • Грамматики языков программирования (Python [2] , Lua [3] )

Пример

Грамматика связей

Грамматика связей — это грамматическая система для классификации естественных языков указывающая связи между последовательностями слов. Вместо использования part-of-speech tags на основе правил для разбора предложений, грамматика связей использует связи для создания синтаксической структуры для языка.

Основная идея

Слова рассматриваются как блоки с выходными разъемами (connectors).

Есть несколько типов разъемов; а также, разъемы могут также указывать вправо, или влево. Раъем указывающий влево соединяется с разъемом, указывающим вправо того же самого типа иного слова. Два разъема вместе формируют «связь» (link).

Разъемы указывающие направо, помечаются знаком «+», указывающие влево — знаком «-«.

Слова имеют правила о том, как их разъемы могут быть соединены, т.е. правила о том, что будет составлять корректное использование данного слова. Корректное предложение — это предложение, в котором все представленные слова используются корректно, в соответствии с их правилами и которые также удовлетворяют определенным глобальным правилам. [4]

Правила для слов (word rules)

Обычная запись в словаре выглядит следующим образом:

Это означает, что если слово «blah» используется в предложении, оно должно формировать связь «A» с другим словом, т.е. должно быть другое слово справа с разъемом (connector) типа «A-«. В противном случае, предложение некорректно. Выражение, следующее за двоеточием — это «требования к связям» (linking requirement) для слова.

Слово может иметь более одного раъема. Это будет обозначаться следующим образом:

Слово может иметь такие правила, что только один из двух (или один из нескольких) разъемов будет использовано, но один из них обязательно должен быть использован. Это обозначается следующим образом:

Это означает что если слово может сделать либо связь типа «А» справа, либо связь типа «B» слева, то его использование в предложении будет корректным, но оно обязано содержать одну из связей и не может сделать обе связи. Эти правила могут быть скомбинированы. Например:

Это означает что слово должно содержать либо связь типа «A» справа, либо связь типа «B» слева и связь типа «С» справа. Другие комбинации будут некорректны.

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

Некоторые раземы опциональны, для этого используются фигурные скобки. Например:

Это означает что слово должно содержать связь типа «А» справа, и оно может содержать связь типа «В» справа, но не обязано содержать её. Фигурные скобки могут также заключать в себе сложные выражения, например:

Эквивалентный способ записи опционального выражения «» следующий: «(X- or ())».

Илон Маск рекомендует:  Что такое код sin

Слово может также создавать неопределенное число связей одного типа с другими словами. Для этого, используется multi-connector символ «@». Например, в следующем примере слово может создавать любое число связей типа F со словами справа (но не обязано содержать их).

(Если слово имеет «@A+», без фигурных скобок, то оно обязано содержать как минимум одну связь типа A (справа), остальные опциональны). Порядок элементов в выражении (connector expression) важен. Он диктует относительную близость (relative closeness) слов, которые будут соединены.

В этом примере слово «blah» должно образовывать связь типа «А» справа и связь типа «B» справа, и слово, образующее связь типа «А» должно быть ближе, чем слово образующее связь типа «В».

Однако, это относится только к соединениям одной направленности. Для разъемов, указывающих в противоположных направлениях, порядок не важен. Поэтому,


означает то же самое, что и:

В этом отношении:

означает то же самое, что:

Для выражений с оператором «or», таких как «A+ or B+», порядок элементов не важен.

Запись в словаре поэтому содержит слово, последующее двоеточие, а затем выражение связей (connector expression), заканчивающееся точкой с запятой. Словарь содержит серию таких записей. Любое число слов может быть помещено в список, разделенный пробелами, и все они будут обладать требованиями на связи *linking requirement):

Имя раъема (connector name) должно содержать одну или несколько заглавных букв (может быть использовано их любое число), с последующими «+» или «-«.

Также следует упомять концепцию «разъединителей» (disjunct). Разъединитель — это набор типов разъемов (connector types), образующих корректное использование слова. Выражение в словаре для любого слова может быть представлено как набор разъединителей (set of disjuncts).

Если, например, слово имеет следующее выражение:

тогда, оно имеет следующие четыре разъединителя:

Эти разъединители отображают все корректные использования слова «blah». Использование C- и A+ — корректно для слова, в то время как использование A+ и B+ некорректно. Разделители играют важную роль во внутренней работе парсера связей.

Глобальные правила (Global rules)

Также как и правила слов («word rules»), которые указаны в словаре, есть два других глобальных правила, которые контролируют, как слова могут быть соединены.

Прежде всего, ссылки не могут пересекаться. Например, следующий способ соединения четырех слов ( соединение «cat» к «dog» и «horse» к «fish») будет неправильным. Парсер просто не найдет таких связей.

Это правило планарности («planarity rule» или «crossing-links»). Во вторых, все слова в предложении должны быть косвенно связаны (indirectly connected) с каждым другим словом. Поэтому следующий путь соединения этих четырех слов также будет некорректным:

Это правило вовлеченности («connectivity» rule). Поэтому, корректное предложение — это предлоежение, которое может быть связано следующими связями:

  • все используемые слова предложении, удовлетворяют правилам связей (linking requirements);
  • не нарушаются правила планарности (crossing-links) и вовлеченности (connectivity).

Грамматика связей и её отношения с другими системами

Структура, назначенная предложению грамматикой связей значительно отличается от других грамматических систем (хотя она связана с грамматикой зависимостей). Вместо того, чтобы размышлять в терминах синтаксических функций (как субъект и объект), или составляющих (например, «глагольная составляющая»), необходимо размышлять в терминах взаимоотношений между парами слов. В предложении ниже, например, есть «S»-отношение (субъект) между «dog» и «has»; отношение «PP» (past-participle) между «has» и «gone»; и «D»-отношение (determiner) между «the» и «dog:

Однако, можно заметить, что части речи, синтаксические функции и составляющие могут быть восстановлены из структуры связей (link structure) довольно просто.

КомбинАторный Синтаксический анализ — II

2. Контекстно-свободные языки и грамматики

Это тоже просто (точнее, это просто на том уровне, на котором я это знаю и излагаю, хотите сложно — читайте Ахоульмана. Я его начинал, но пока не осилил).

2.1. Введение в проблематику

Сначала несколько тупых определений.

Алфавит — набор символов (конечное множество, если вам так проще).

Например:

  • <0, 1>алфавит из двух символов: 0 и 1
  • <'(', ')'>алфавит из правой и левой скобки
  • алфавит, состоящий из букв английского алфавита
  • <'(', ')', '+', '*', '-', '/', 0, 1, .. 9>алфавит, состоящий из скобок, арифметических операторов и цифр

Цепочка — конечная (возможно, пустая) последовательность символов некоторого алфавита (не уверен, что конечность обязательна). Примеры как-нибудь сами придумаете :) Пустая цепочка обычно обозначается буквой эпсилон. Я буду обозначать её как ».

Язык — множество «правильных» цепочек. Как именно задаётся правильность — да как угодно. Говорят, что язык определён над алфавитом. Т.е. типа: «.. пусть задан язык L над алфавитом Z. » (только по традиции, вместо Z должна быть заглавная сигма..).

Например:

  • <'0', '1'>язык из двух цепочек: ‘0’ и ‘1’
  • <'0', '1', ''>язык из трёх цепочек: ‘0’, ‘1’ и пустая цепочка
  • язык, которому принадлежат все возможные цепочки из символов 0 и 1
  • язык, над алфавитом <0, 1>, которому принадлежат все цепочки из 0 и 1, содержащие простое число (все помнят, кто такие простые числа?) единичек
  • язык над «арифметическим» алфавитом, содержащий все цепочки, являющиеся корректными арифметическими выражениями. Корректные с точки зрения синтаксиса, т.е. чтобы все скобки закрыты, а знаки с числами некоторым образом чередуются (например, не встречается подряд два знака умножения)
  • такой же как в предыдущем пункте. Но чтобы все выражения были вычислимы :) Т.е. чтобы нигде не получалось деления на 0.

Контекстно-свободная (КС) грамматика — один из способов задания языка. Чтобы задать язык нужно указать его алфавит и сформулировать правила для цепочек. Алфавит задаётся тупо перечислением, самое интересное это, конечно, правила, КС-грамматики предлагают один из способов их формулировки. Далеко не все языки можно задать таким образом, те, которые можно, называют КС-языками.

2.2. Формальное определение и пара слов

КС-грамматика состоит из четырёх частей:

  • Множество терминальных символов T (алфавит языка)
  • Множество нетерминальных символов N (узнаете..)
  • Начальный символ S, принадлежащий N
  • Множество правил.

Правила имеют вид:

Где:

  • X принадлежит N
  • yi принадлежит либо N, либо T
  • n >= 0

Как это всё работает проще объяснять в сторону генерации. Тогда правила это просто подстановки. Алгоритм действий:

  1. Берём начальный символ S. Это наша исходная цепочка.
  2. Просматриваем текущую цепочку, находим в ней нетерминальный символ X (не обязательно первый по очереди, можно любой).
  3. Находим правила, содержащие этот символ слева. Т.е правила вида X = . выбираем одно из них. Если нет нет ни одного, то этой генерации каюк, цепочку нам уже не закончить. Если не закончить ни одну цепочку, то грамматика задаёт пустой язык.
  4. Подставляем вместо X в соответствующую позицию цепочки правую часть правила.
  5. Если в цепочке ещё есть нетерминальные символы, goto 2
  6. Конец.

Особенность КС-грамматик в том, что правила не зависят от контекста (потому и называются — контекстно свободные). В любом месте цепочки, в любом окружении нетерминальный символ заменяется по одним и тем же правилам. Это ограничивает множество языков, которые можно задать КС-грамматиками, но зато очень облегчает обработку.

2.3. Примеры

2.3.1 Первый

1. Берём S
2. Применяем первое правило. S -> aSb
3. Находим нетерминал.. Опять S! Применяем первое правило aSb -> aaSbb
4. Находим нетерминал.. Опять S! Применяем второе правило aaSbb -> aabb
5. Нет нетерминалов, конец.

Ну, в общем, понятно, что получается? », ‘ab’, ‘aabb’, ‘aaabbb’, . a n b n , ..

2.3.2. Второй

Правила:
S = E
E = M
E = E ‘+’ E
M = a
M = b
M = M ‘*’ M
M = ‘(‘ E ‘)’

Если я нигде не ошибся, должно получаться множество арифметических выражений со знаками + и * над буквами a и b. E от слова expression, M от multiplication. По классике вместо M пишут T, от слова term, но к сожалению T уже занята.

2.4. Деревья

Казалось бы, причём тут деревья? А оказывается, что очень даже причём. Процесс генерации цепочки аналогичен построению следующего дерева (все знают, кто такие деревья?):

  • Корень — S
  • При применении правила, заменяющего нетерминал X на цепочку y1y2. yn, в дерево добавляются узлы y1y2. yn, они становятся детьми узла, содержащего X.

В результате:

  • Крона (узлы, не имеющие детей) дерева — текущее состояние цепочки
  • К концу генерации в листьях находятся только нетерминалы и символы «пустая строка»
  • По дереву невозможно восстановить последовательность применения правил в разных ветках. Впрочем, этот порядок ни на что и не влияет.
  • Но вот каждую ветку можно восстановить точно

Вот так выглядят деревья для примеров из предыдущего пункта:
иВ общем, идея должна быть ясна.

В качестве примечания: соответствие дерево цепочка всегда однозначно, дерево точно определяет цепочку. А вот соответствие цепочка дерево — не всегда. Например, в приведённой выше грамматике цепочку a+b+a можно получить двумя способами:
Отличия кажутся незначительными.. До тех пор, пока ‘+’ обозначает ассоциативную операцию, т.е. пока (a+b)+a = a+(b+a) В некоторых случаях это не верно даже для обычного плюса. Ещё смешнее получается если заменить ‘+’ на ‘-‘.

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

Контекстно-свободная грамматика — Context-free grammar

В формальном языке теории, контекстно-свободная грамматика ( CFG ) определенный тип формальной грамматики : набор продукционных правил , которые описывают все возможные строки в данном формальном языке. Правила производства простые замены. Например, правило

заменяет с . Там может быть несколько правил замены для любого заданного значения. Например, A <\ Displaystyle A>α

означает , что может быть заменен либо или . A <\ Displaystyle A>α <\ Displaystyle \ альфа>β

В контекстно-свободных грамматик, все правила один-к-одному, один-ко-многим, или один-к-ни. Эти правила могут применяться независимо от контекста. Левая часть правила производства всегда нетерминал символ. Это означает , что символ не появляется в результате формального языка. Таким образом , в нашем случае, наш язык содержит буквы и , но не α <\ Displaystyle \ альфа>β <\ Displaystyle \ бета>A ,

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

Ниже приведен пример контекстно-свободной грамматики , которая описывает все двухбуквенные строки , содержащие буквы или . α <\ Displaystyle \ альфа>β

Если мы начнем с нетерминальному символа , то мы можем использовать правило , чтобы включить в . Затем мы можем применить один из двух последующих правил. Например, если мы применим к первому мы получаем . Если мы затем применить ко второму мы получаем . Так как и терминальные символы, и в контекстно-свободных грамматик терминальные символы никогда не появляются на левой стороне правила производства, нет больше правил , которые могут быть применены. Такой же процесс может быть использован, применяя последние два правил в различных порядках, чтобы получить все возможные строки в нашей простой контекстно-свободной грамматике. S <\ Displaystyle S>S → A A <\ Displaystyle S \ \ к \ AA>S <\ Displaystyle S>A A <\ Displaystyle AA>A → β <\ Displaystyle А \ \ к \ \ бета>A <\ Displaystyle A>β A <\ Displaystyle \ бета A>A → α <\ Displaystyle А \ \ к \ \ альфа>A <\ Displaystyle A>β α <\ Displaystyle \ бета \ альфа>α <\ Displaystyle \ альфа>β

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

Контекстно-свободных грамматик возникают в лингвистике , где они используются для описания структуры предложений и слов в естественном языке , и они были на самом деле изобрел лингвиста Ноама Хомского для этой цели, но на самом деле не дожил до их первоначального ожидания. В противоположность этому , в информатике , так как использование рекурсивно определенных понятий увеличивается, они были использованы все больше и больше. В начале применения грамматика используется для описания структуры языков программирования . В новой заявке, они используются в качестве существенной части Extensible Markup Language (XML) называются определение типа документа .

В лингвистике , некоторые авторы используют термин фразы структуру грамматику для обозначения контекстно-свободных грамматики, причем разговорник структура грамматика , отличные от грамматик зависимостей . В информатике , популярная нотация для контекстно-свободных грамматик Backus-Наура , или BNF .

содержание

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

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

может быть логически скобки следующим образом:

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

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

Контекстно-свободные грамматики представляют собой особый вид Semi-Туя систем , которые в своей общей форме дате назад к работе Axel Thue .

Формализм контекстно-свободных грамматик был разработан в середине 1950-х годов по Ноама Хомского , а также их классификацию как особый тип из формальной грамматики (которую он назвал фразу-структуры грамматики ). Что Хомский называется фраза структура грамматики также известна теперь как грамматика избирательного округа, в котором окружные грамматик стоят в отличие от грамматик зависимостей . В Хомской порождающей грамматике рамке, синтаксис естественного языка был описан контекстно-свободными правилами в сочетании с правилами преобразования.

Блочная структура была введена в компьютер языков программирования со стороны Алголя проекта (1957-1960), который, как следствие, также показал контекстно-свободной грамматики , чтобы описать полученный синтаксис Algol. Это стало стандартной функцией компьютерных языков, а также обозначения для грамматик , используемых в конкретных описаниях компьютерных языков стали известны как Backus-Наура , после двух членов языкового дизайна комитета Алголь. «Блочная структура» аспект, контекстно-свободная грамматика захват настолько фундаментален грамматика , что синтаксис и грамматика терминов часто отождествляют с контекстно-свободными грамматическими правилами, особенно в области информатики. Формальные ограничения не захваченные грамматика, затем считается частью «семантикой» языка.

Контекстно-свободные грамматики достаточно просты , чтобы построение эффективных алгоритмов синтаксического анализа , что для данной строки, определить , можно ли и как он генерируется из грамматики. Эрли анализатор является примером такого алгоритма, в то время как широко используемые LR и LL — парсеры более простые алгоритмы , которые имеют дело только с более ограничительными подмножеств контекстно-свободных грамматик.

Формальные определения

Контекст-свободная грамматика G определяется 4- кортежа :

Правило производства нотация

Правило производства в R формализуется математически в виде пары , где находится нетерминальный и является строкой переменных и / или терминалов; а не с помощью упорядоченной пары обозначения, правила производства, как правило , написаны с использованием оператора со стрелкой с & alpha ; в качестве его левой стороны и р в его правой части: . ( α , β ) ∈ р <\ Displaystyle (\ альфа, \ бета) \ в R>α ∈ В <\ Displaystyle \ альфа \ в V>β ∈ ( В ∪ Σ ) * <\ Displaystyle \ бета \ в (V \ чашку \ Sigma) ^ <*>> α → β

Допускается для р быть в пустую строку , и в этом случае принято обозначать через е. Форма называется ε -производство. α → ε

Обычно , чтобы перечислить все правый для одной и той же левой стороны на ту же линию, используя | ( символ трубы ) , чтобы отделить их. Правила и , следовательно , можно записать в виде . В этом случае, и называются первым и вторым вариантом, соответственно. α → β 1 <\ Displaystyle \ альфа \ СтрелкаВправо \ бета _ <1>> α → β 2 <\ Displaystyle \ альфа \ СтрелкаВправо \ бета _ <2>> α → β 1 | β 2 <\ Displaystyle \ альфа \ СтрелкаВправо \ бета _ <1>\ середина \ бета _ <2>> β 1 <\ Displaystyle \ бета _ <1>> β 2 <\ Displaystyle \ бета _ <2>>

применение правила

Серийное применение правила

Свободный язык

Язык грамматики есть множество г знак равно ( В , Σ , р , S )

Язык L называется контекстно-свободный язык (CFL), если существует CFG G , такой , что . L знак равно L ( г )

Правильные CFGs

Контекстно-свободная грамматика называется собственно , если он имеет

Каждый контекстно-свободная грамматика может быть эффективно преобразована в слабо эквивалентный один без недостижимых символов, слабо эквивалентный без непроизводительных символов и слабо эквивалентной без циклов. Каждый контекстно-свободная грамматика не производит ε может быть эффективно преобразовано в слабо эквивалентный без е-производств; в целом, каждая такая грамматика может быть эффективно преобразовано в слабо эквивалентной правильной CFG.

Примеры

Слова сцепляются с их реверсом

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

Это ясно показывает, что . Язык является контекстно-свободной, однако, это может быть доказано , что это не регулярный . L ( г ) знак равно < вес вес р : вес ∈ < a , б >* > <\ Displaystyle L (G) = \ : ш \ в \ <а, Ь \>^ <*>\>>

добавлены, контекстно-свободной грамматики для множества всех палиндромов в алфавите < , Ь > получается.

Корректность круглые скобки

Канонический пример контекстно-свободной грамматики соответствия скобка, который является представителем в общем случае. Есть два терминальные символы «(» и «)» и один нетерминал символ S. Правила производственных

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

Хорошо сформированный вложенные скобки и квадратные скобки

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

S → С.С. S → () S → (S), S → [] S → [S]

с терминальными символами [] () и нетерминальным S.

Следующая последовательность может быть получена в этой грамматике:

Соответствующие пары

В контекстно-свободной грамматике, мы можем паре символы, как мы делаем с кронштейнами . Самый простой пример:

Специальный символ ε обозначает пустую строку. Изменяя выше грамматику

мы получим грамматику , порождающую язык вместо этого. Это отличается только тем , что она содержит пустую строку , в то время как оригинальная грамматика не сделала. < a N б N : N ≥ 0 > <\ Displaystyle \ <а ^ <п>Ь ^ <п>п \ GEQ 0 \>>

Отдельное число а х и б х

Контекст-свободная грамматика для языка, состоящего из всех строк над <а, Ь>, содержащие неравное количество элементов а и Б:

S → U | В U → TAU | TaT | UAT V → TBV | ТБТ | Vbt T → aTbT | bTaT | ε

Здесь нетерминал Т может генерировать все строки с тем же числом элементов а как Б, нетерминал U генерирует все строки с больше, чем б-х-х и нетерминалом V генерирует все строки с меньшим количеством, чем через е года б. Опуская третью альтернативу правилу U и V не ограничивает язык в грамматики.

Второй блок Б двойного размера

Другой пример нерегулярного языка . Это контекстно-свободный , как это может быть сгенерировано следующей контекстно-свободной грамматикой: < б N a м б 2 N : N ≥ 0 , м ≥ 0 > <\ Displaystyle \ <Ь <п>а ^ <т>Ь ^ <2n>: п \ GEQ 0, т \ GEQ 0 \>>

S → bSbb | → аА | ε

логические формулы первого порядка

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

Примеры языков, которые не являются контекстно-свободной

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

Тот факт , что этот язык не является контекстно свободным может быть доказано с помощью Насосной леммы для контекстно-свободных языков и доказательства от противного, заметив , что все слова вида должны принадлежать к языку. Этот язык принадлежит вместо более общего класса и может быть описан конъюнктивной грамматикой , которая , в свою очередь , также включает в себя другие , не контекстно-свободных языков, такие как язык всех слов вида . ( N [ N ) N ] N <\ Displaystyle <(>^ <п> <[>^ <п> <)>^ <]>^ <п>> a N б N с N <\ Displaystyle а ^ <п>Ь <п>с ^ <п>>

Регулярные грамматики

Каждая регулярная грамматика является контекстно-свободной, но не все контекстно-свободные грамматики являются регулярными. Следующий контекстно-свободной грамматики, однако, также регулярно.

S → A S → AS S → Б.С.

Терминалы здесь и б , в то время как только нетерминал является С. Язык Описанная все непустые строки с и х , которые заканчиваются . a <\ Displaystyle а>б <\ Displaystyle Ь>a

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

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

Использование символов трубы, грамматика выше, может быть описана более сжато следующим образом:

Дифференцирования и синтаксические деревья

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

Вывод полностью определяется заданием, для каждого шага:

  • правило применяется в этом шаге
  • возникновение его левой части, к которой она применяется

Для ясности, промежуточная строка обычно дается как хорошо.


Например, с грамматикой:

могут быть получены с выводом:

Часто, стратегия следует, что детерминировано определяет следующий нетерминал переписать:

  • в крайнем левом выводе , это всегда крайняя левая нетерминал;
  • в крайнем правом выводе , это всегда крайний правый нетерминал.

Учитывая такую ​​стратегию, дифференцирование полностью определяется последовательностью правил, применяемых. Например, крайний левый вывод

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

Вывод также налагает в некотором смысле иерархическую структуру на строку, которая является производным. Например, если строка «1 + 1 + а» происходит по крайней левый вывод:

S → S + S (1) → 1 + S (2) → 1 + S + S (1) → 1 + 1 + S (2) → 1 + 1 + а (3)

структура строки будет выглядеть так:

где <. >S обозначает подстрока признается принадлежность к S. Этой иерархии может также рассматриваться как дерево:

Это дерево называется дерево разбора или «конкретный синтаксис дерево» из строки, в отличие от абстрактного синтаксического дерева . В этом случае представлена крайние левые и правые производные определяют один и то же дерево разбора; Однако, существует еще один (самый правый) вывод одной и той же строки

S → S + S (1) → S + а (3) → S + S + а (1) → S + 1 + а (2) → 1 + 1 + а (2)

и это определяет следующее дерево разбора:

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

S → S + S (1) → S + S + S, (1) → 1 + S + S (2) → 1 + 1 + S (2) → 1 + 1 + а (3)

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

Пример: Алгебраические выражения

Вот контекстно-свободная грамматика для синтаксически правильных инфиксные алгебраических выражений в переменных х, у и г:

Эта грамматика может, например, генерировать строку

(Х + у) * х — г * г / (х + х)

S (начальный символ) → S — S (в соответствии с правилом 5) → S * S — S (по правилу 6, применяется к крайней левой S) → S * S — S / S (в соответствии с правилом 7, применяется к самой правой S) → (S), S * — S / S (по правилу 8, применяется к крайней левой S) → (S), S * — S / (S) (в соответствии с правилом 8, применяется к самой правой S) → (S + S) * S — S / (S), (и т.д.) → (S + S) * S — S * S / (S), → (S + S) * S — S * S / (S + S) → (х + S), S * — S * S / (S + S) → (х + у) * S — S * S / (S + S) → (х + у) * х — С * г / (S + S) → (х + у) * х — С * г / (х + S), → (х + у) * х — г * г / (х + S), → (х + у) * х — г * г / (х + х)

Обратите внимание, что многие варианты были сделаны в стадии реализации, как, к которому переписывает собирались проводить дальше. Эти варианты выглядят весьма произвольно. По сути, они являются, в том смысле, что строка, наконец, генерируется всегда одинакова. Например, второй и третий переписывает

→ S * S — S (по правилу 6, применяется к крайней левой S) → S * S — S / S (в соответствии с правилом 7, применяется к самой правой S)

может быть сделано в обратном порядке:

→ S — S / S (в соответствии с правилом 7, применяется к самой правой S) → S * S — S / S (по правилу 6, применяется к крайней левой S)

Кроме того , многие варианты были сделаны на какое правило применить к каждой выбранной S . Изменение выбора , сделанный и не только порядок они были сделаны в обычно аффекты , которые терминальная цепочка выходит в конце.

Давайте посмотрим на это более подробно. Рассмотрим дерево разбора этого вывода:

Начиная с верхнего, шаг за шагом, втор в дереве расширяется, пока не более нерасширенные S ES (нетерминалы) остаются. Выбор другого порядка расширения будет производить другой вывод, но то же дерево разбора. Дерево разбора изменится только тогда , когда мы выбираем другое правило для применения в какой — то позиции в дереве.

Но может отличаться дерево синтаксического анализа до сих пор производит терминальную строку, которая ( x + y ) * x — z * y / ( x + x ) в этом случае? Да, для этой конкретной грамматики, это возможно. Грамматик с этим свойством называется неоднозначно .

Например, x + y * z могут быть получены с этих двух различных деревьев разбора:

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

Т → х T → Y T → г S → S + T, S → S — Т S → S * T S → S / T T → (S), S → T

(еще раз выбирая в S качестве стартового символа). Эта альтернативная грамматика будет производить x + y * z с деревом разбора аналогичен левой выше, т.е. неявно предполагая связь (x + y) * z , которая не в соответствии со стандартом старшинства операторов. Более сложные, однозначные и контекстно-свободные грамматики могут быть построены , которые производят дерева разбора , которые подчиняются все желательная очередность оператора и ассоциативности правила.

Нормальные формы

Каждая контекстно-свободная грамматика , которая не создает пустую строку может быть преобразована в один , в котором нет е-производства (то есть правило , которое имеет пустую строку в качестве продукта). Если грамматика делает генерировать пустую строку, будет необходимо включить правило , но не должно быть никакого другого ε-правилом. Каждый контекстно-свободная грамматика, без е-производства имеет эквивалентную грамматику в нормальной форме Хомского и грамматику в Greibach нормальной форме . «Эквивалент» здесь означает , что две грамматики порождают один и тот же язык. S → ε

Особенно простая форма продукционных правил в нормальной форме Хомского грамматика имеет как теоретические , так и практические последствия. Например, с учетом контекстно-свободной грамматики, можно использовать обычную форму Чомски построить полиномиальный алгоритм , который решает , является ли данная строка на языке , представленного этой грамматике или нет ( алгоритм CYK ).

свойства Затворы

Бесконтекстные языки закрыты в соответствии с различными операциями, то есть, если языки К и L является контекстно-свободным, так что является результатом следующих операций:

Они не закрыты под общим пересечением (следовательно , ни при комплементации ) и установленной разнице.

Разрешимые проблемы

Ниже приведены некоторые разрешимые проблемы о контекстно-свободных грамматик.

анализ

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

Контекстно-свободной анализа для нормальной форме Хомского грамматик показал Лесли Г. Отважном быть сводится к булевой матричного умножения , таким образом , наследует его сложность верхняя граница O ( п 2.3728639 ). И наоборот, Лиллиан Ли показал O ( п 3-е ) логическое умножение матриц быть сводится к O ( п 3-3ε ) CFG синтаксического анализа, таким образом устанавливая какой — то нижняя граница для последнего.

Достижимость, производительная, допустимость пустых

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

Регулярность и LL ( K ) проверяет

Это разрешимо ли данная грамматика является регулярной грамматикой , а также является ли это LL ( к ) грамматикой для данных к ≥ 0. Если к не задана, последняя проблема неразрешима.

Учитывая контекстно-свободный язык , он не является ни разрешим ли это регулярно, и не является ли это LL ( K ) языком для заданных к .

Пустота и конечность

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

Неразрешимые проблемы

Некоторые вопросы, которые неразрешимы для более широких классов грамматика становится разрешима для контекстно-свободных грамматик; например, проблема пустоты (генерируется ли грамматика любых терминала строк вообще), неразрешима для контекстно-зависимых грамматик , но разрешимая для контекстно-свободных грамматик.

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

Всеобщность

Учитывая CFG, она генерирует язык всех строк над алфавитом терминальных символов, используемых в его правилах?

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

Язык равенство

Учитывая две CFGs, они порождают один и тот же язык?

Неразрешимость этой проблемы является прямым следствием предыдущим: это невозможно даже решить, будет ли CFG эквивалентен тривиальным CFG, определяющего язык всех строк.

включение Язык

Учитывая два CFGs, может первый генерировать все строки, второй может генерировать?

Если эта проблема разрешима, то язык равенство может быть решено слишком: два CFGs G1 и G2 порождают один и тот же язык, если L (G1) представляет собой подмножество L (G2) и L (G2) является подмножеством L (G1).

Находясь в более низком или более высоком уровне иерархии Хомского

Используя теорему Greibach в , можно показать , что две следующие проблемы неразрешимы:

  • Учитывая контекстно-зависимая грамматика , не описывает контекстно-свободный язык?
  • Учитывая контекстно-свободной грамматики, она описывает регулярный язык ?

Грамматика неоднозначность

Неразрешимость этой проблемы вытекает из того факта , что если алгоритм определения существует неоднозначность, то переписка проблема Сообщение может быть принято решение, которое , как известно, неразрешима.

Язык дизъюнктность

Учитывая два CFGs, есть ли строка выводима из обоего грамматик?

Если эта проблема разрешима, неразрешимость сообщение переписка проблема может быть принято решение, тоже: данные строки над некоторым алфавитом , пусть грамматика состоит из правила α 1 , . , α N , β 1 , . , β N <\ Displaystyle \ альфа _ <1>, \ ldots, \ альфа _ , \ бета _ <1>, \ ldots, \ бета _ > < a 1 , . , a К ><\ Displaystyle \ <а_ <1>, \ ldots, а_ <к>\>> г 1 <\ Displaystyle G_ <1>>

Тогда проблема Сообщение дается имеет решение тогда и только тогда , когда и разделяют выводимая строка. α 1 , . , α N , β 1 , . , β N <\ Displaystyle \ альфа _ <1>, \ ldots, \ альфа _ , \ бета _ <1>, \ ldots, \ бета _ > L ( г 1 ) <\ Displaystyle л (G_ <1>)> L ( г 2 ) <\ Displaystyle л (G_ <2>)>

расширения

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

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

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

Подклассы

Есть целый ряд важных подклассов контекстно-свободных грамматик:

  • LR ( к ) грамматик (также известная как детерминированные контекстно-свободные грамматики ) позволяет разбор (распознаванию строки) с детерминированным магазинным автоматом (PDA), но они могут описывать только детерминированные контекстно-свободные языки .
  • Простой LR , упреждающая LR грамматик являются подклассами , которые позволяют дальнейшее упрощение анализа. SLR и LALR распознаются с использованием той же КПК , как LR, но с более простыми таблицами, в большинстве случаев.
  • LL ( K ) и LL ( * ) грамматик позволяет синтаксический анализ путем прямого построением левого вывода , как описано выше, и описать даже меньше языков.
  • Простые грамматики являются подклассом LL (1) грамматика основном интересна своей теоретической собственности , что язык равенство простых грамматик разрешимо, в то время как включение языка не является.
  • В квадратных скобках грамматики имеют свойство , что терминальные символы разделены на левые и правый пар скобок , которые всегда совпадают в правилах.
  • Линейные грамматики не имеют правил с более чем одной нетерминалом на правой стороне.
  • Регулярные грамматики являются подклассом линейных грамматик и описывают регулярные языки, то есть они соответствуют конечным автоматам и регулярные выражения .

LR синтаксического анализ расширяет LL синтаксический анализ для поддержки большего диапазона грамматик; в свою очередь, обобщенный LR разборе расширяет LR синтаксический для поддержки произвольных контекстно-свободных грамматик. На LL грамматик и LR — грамматик, она по существу выполняет синтаксический анализ LL и LR синтаксического анализа, соответственно, в то время как на недетерминированных грамматик , это так эффективно , как можно ожидать. Хотя РВО разборе был разработан в 1980 — х годах, многие определения нового языка и парсер генераторы продолжают основываться на LL, LALR или LR разбор вплоть до сегодняшнего дня.

Лингвистические приложения

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

Такие правила являются еще одним стандартным устройством в традиционной лингвистике; например passivization на английском языке. Большая часть порождающей грамматики была посвящена поиску путей уточнения описательные механизмов грамматики и трансформационных правил разговорник структуры таким образом, что именно те вещи могут быть выражены , что естественный язык действительно позволяет. Разрешение произвольных преобразований не отвечает этой цели: они слишком мощные, будучи Тьюринга , если существенные ограничения не добавляются (например , не преобразования , которые вводят , а затем переписать символы в контекстно-свободной моды).

Общая позиция Хомского относительно отсутствия контекстной свободности естественного языка занимал до тех пор, хотя его конкретные примеры , касающиеся неадекватности контекстно-свободных грамматик с точки зрения их слабой порождающей способности были впоследствии опровергнуты. Джералд Газдар и Джеффри Pullum утверждают , что несмотря на некоторых не-контекстно-свободные конструкции на естественном языке (например, кросс-серийные зависимости в швейцарском немецком и удвоении в Bambara ), подавляющее большинство форм на естественном языке действительно контекстно-свободные.

Лекція 6.Контекстно-свободные грамматики и автоматы с магазинной памятью

Читайте также:

  1. Автоматные грамматики и конечные автоматы
  2. АЛУ с сосредоточенной памятью и логикой
  3. Конечные автоматы
  4. Контекстно-свободные грамматики и языки
  5. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ
  6. Лекція 1. Буддизм: основи віровчення і культу
  7. Лекція 1. Виникнення та еволюція християнства
  8. Лекція 1. Іслам: особливості віровчення і культу
  9. ЛЕКЦІЯ 1. Краєзнавство як наука.
  10. Лекція 1. Неорелігії. Секуляризація і свободомислення в історії суспільства. Релігія і церква в системі державно-правових відносин.
  11. Лекція 1. Нетрадиційна релігійність та Україна
  12. Лекція 1. Пізні національні релігії

Пусть G = (N, T, P, S) — КС-грамматика. Введем несколько важных понятий и определений.

Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним. Если S=> * u в процессе левостороннего вывода, то u — левая сентенциальная форма. Аналогично определим правосторонний вывод. Обозначим шаги левого (правого) вывода =>l (=>r).

Упорядоченным графом называется пара (V,E), где V есть множество вершин, а E — множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v1), (v, v2), . , (v, vn)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1, второй — дуга, входящая в вершину v2, и т.д.

Упорядоченным помеченным деревом называется упорядоченный граф (V,E), основой которого является дерево и для которого определена функция f : V -> F (функция разметки) для некоторого множества F.

Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора ) цепочки w в КС-грамматике G = (N, T, P, S), если выполнены следующие условия:

(1) корень дерева D помечен S ;

(2) каждый лист помечен либо , либо e ;

(3) каждая внутренняя вершина помечена нетерминалом ;

(4) если X — нетерминал, которым помечена внутренняя вершина и X1, . , Xn — метки ее прямых потомков в указанном порядке, то X -> X1 . Xk — правило из множества P ;

(5) Цепочка, составленная из выписанных слева направо меток листьев, равна w.

Процесс определения принадлежности данной строки языку, порождаемому данной грамматикой, и, в случае указанной принадлежности, построение дерева разбора для этой строки, называется синтаксическим анализом. Можно говорить о восстановлении дерева вывода (в частности, правостороннего или левостороннего) для строки, принадлежащей языку. По восстановленному выводу можно строить дерево разбора.

Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.

Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что для некоторой цепочки R существует вывод .

Автомат с магазинной памятью (МП-автомат) — это семерка , где

(1) Q — конечное множество состояний, представляющих всевозможные состояния управляющего устройства;

(2) T — конечный входной алфавит;

(3) — конечный алфавит магазинных символов ;

(4) D — отображение множества в множество конечных подмножеств , называемое функцией переходов ;

(5) — начальное состояние управляющего устройства;

(6) — символ, находящийся в магазине в начальный момент ( начальный символ магазина );

(7) — множество заключительных состояний.

Конфигурация МП-автомата — это тройка (q, w, u), где

(1) — текущее состояние управляющего устройства;

(2) — непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = e, то считается, что вся входная лента прочитана;

(3) — содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считается пустым.

Такт работы МП-автомата M будем представлять в виде бинарного отношения , определенного на конфигурациях.

если множество D(q, a, Z) содержит (p, v), где и (верхушка магазина слева).

Начальной конфигурацией МП-автомата M называется конфигурация вида (q, w, Z), где , то есть управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине имеется только начальный символ Z.

>Заключительной конфигурацией называется конфигурация вида (q, e, u), где , то есть управляющее устройство находится в одном из заключительных состояний, а входная цепочка целиком прочитана.

Введем транзитивное и рефлексивно-транзитивное замыкание отношения , а также его степень k > 0 (обозначаемые , и соответственно).

Говорят, что цепочка w допускается МП-автоматом M, если для некоторых и .

Множество всех цепочек, допускаемых автоматом M называется языком, допускаемым (распознаваемым, определяемым) автоматом M (обозначается L(M) ).

Пример 4.1. Рассмотрим МП-автомат

у которого функция переходов D содержит элементы:

Нетрудно показать, что , где w R обозначает обращение («переворачивание») цепочки w.

Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M, если для некоторого . В таком случае говорят, что автомат допускает цепочку опустошением магазина. Эти определения эквивалентны, ибо справедлива

Теорема 4.1. Язык допускается МП-автоматом тогда и только тогда, когда он допускается (некоторым другим автоматом) опустошением магазина.

Доказательство. Пусть L = L(M) для некоторого МП- автомата . Построим новый МП- автомат M’, допускающий тот же язык опустошением магазина.


Пусть где функция переходов D’ определена следующим образом:

  1. Если , то для всех и (моделирование М ),
  2. (начало работы),
  3. Для всех и множество D'(q, e, Z) содержит (qe, e) (переход в состояние сокращения магазина без продвижения),
  4. D'(qe, e, Z) = <(qe, e)> для всех , (сокращение магазина).

Автомат сначала переходит в конфигурацию соответственно определению D’ в п.2, затем в ,

соответственно п.1, затем в соответственно п.3, затем в (qe, e, e) соответственно п.4. Нетрудно показать по индукции, что (где ) выполняется для автомата M тогда и только тогда, когда выполняется для автомата M’. Поэтому L(M) = L’, где L’ — язык, допускаемый автоматом M’ опустошением магазина.

Обратно, пусть — МП — автомат, допускающий опустошением магазина язык L. Построим автомат M’, допускающий тот же язык по заключительному состоянию.

Пусть , где D’ определяется следующим образом:

  1. — переход в «режим M «,
  2. Для каждого определим — работа в «режиме M » ,
  3. Для всех — переход в заключительное состояние.

Нетрудно показать по индукции, что L = L(M’). Одним из важнейших результатов теории контекстно-свободных языков является доказательство эквивалентности МП-автоматов и КС-грамматик.

Теорема 4.2. Язык является контекстно-свободным тогда и только тогда, когда он допускается МП-авто- матом.

Доказательство.(алгоритм побудови мп-автомату по КВ граматиці). Пусть G = (N, T, P, S) — КС-граммати- ка. Построим МП-автомат, допускающий язык L(G) опустошением магазина.

Пусть , где D определяется следующим образом:

Фактически, этот МП-автомат в точности моделирует все возможные выводы в грамматике G. Нетрудно показать по индукции, что для любой цепочки вывод S => + w в грамматике G существует тогда и только тогда, когда существует последовательность тактов автомата M.

Алгоритм побудови Кв граматики по мп-автомату)

Наоборот, пусть дан — МП- автомат, допускающий опустошением магазина язык L.

Построим грамматику G, порождающую язык L.

Пусть , где P состоит из правил следующего вида:

Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левосторонний вывод w в грамматике G.

Индукцией по числу шагов вывода в G или числу тактов M нетрудно показать, что тогда и только тогда, когда [qAp] => + w.

Тогда, если , то S => [qZq] => + w для некоторого . Следовательно, и поэтому . Аналогично, если , то . Значит, S =>[qZq] => + w, и поэтому .

| следующая лекция ==>
Выпускная квалификационная работа | Этапы физиологической адаптации к учебным нагрузкам, особенности адаптации на разных этапах возрастного развития. Закономерности адаптации и организация учебного процесса

Дата добавления: 2014-01-03 ; Просмотров: 335 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Синтаксический анализ

Синтаксический анализ (парсинг) — преобразование последовательности символов на естественном или искусственном языке в соответствии с формальной грамматикой. Англоязычный термин parsing образован от латинского pars ōrātiōnis, означающего «часть речи».

Найдите научные статьи по этой теме в трудах российских NLP-конференций.

Содержание

Контекстно-свободные грамматики

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

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

КС-язык

Дерево вывода

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

Алгоритм построения дерева вывода грамматики выглядит следующим образом.

Порядок нумерации ярусов дерева: корень дерева располагается в нулевом ярусе. Вершины дерева, смежные с корнем образуют первый ярус и т.д. Дуги, выходящие из вершин i <\displaystyle i>-го яруса, ведут к вершинам i + 1 <\displaystyle i+1>яруса.

Высотой дерева называется максимальная длина пути от корня дерева к листу (т.е. номер последнего яруса).

Применение контекстно-свободных грамматик

Контекстно-свободные грамматики хорошо зарекомендовали себя в задачах разбора многих западноевропейских языков, таких как английский.

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

Машинный разбор предложения с использованием контекстно-свободных грамматик реализуется при помощи алгоритма Эрли или алгоритма Кока — Янгера — Касами.

Примеры КС-грамматик

  • Язык Дика (последовательность правильных расстановок скобок)

Язык Дика описывается грамматикой следующего вида:

  • Язык арифметических выражений

Пример грамматики, генерирующей строки, представляющие арифметические выражения со следующими операциями: + , − , ∗ , / <\displaystyle +,-,*,/>и числами как операндами.

  • Лямбда-исчисление [1] .
  • Грамматики языков программирования (Python [2] , Lua [3] )

Пример

Грамматика связей

Грамматика связей — это грамматическая система для классификации естественных языков указывающая связи между последовательностями слов. Вместо использования part-of-speech tags на основе правил для разбора предложений, грамматика связей использует связи для создания синтаксической структуры для языка.

Основная идея

Слова рассматриваются как блоки с выходными разъемами (connectors).

Есть несколько типов разъемов; а также, разъемы могут также указывать вправо, или влево. Раъем указывающий влево соединяется с разъемом, указывающим вправо того же самого типа иного слова. Два разъема вместе формируют «связь» (link).

Разъемы указывающие направо, помечаются знаком «+», указывающие влево — знаком «-«.

Слова имеют правила о том, как их разъемы могут быть соединены, т.е. правила о том, что будет составлять корректное использование данного слова. Корректное предложение — это предложение, в котором все представленные слова используются корректно, в соответствии с их правилами и которые также удовлетворяют определенным глобальным правилам. [4]

Правила для слов (word rules)

Обычная запись в словаре выглядит следующим образом:

Это означает, что если слово «blah» используется в предложении, оно должно формировать связь «A» с другим словом, т.е. должно быть другое слово справа с разъемом (connector) типа «A-«. В противном случае, предложение некорректно. Выражение, следующее за двоеточием — это «требования к связям» (linking requirement) для слова.

Слово может иметь более одного раъема. Это будет обозначаться следующим образом:

Слово может иметь такие правила, что только один из двух (или один из нескольких) разъемов будет использовано, но один из них обязательно должен быть использован. Это обозначается следующим образом:

Это означает что если слово может сделать либо связь типа «А» справа, либо связь типа «B» слева, то его использование в предложении будет корректным, но оно обязано содержать одну из связей и не может сделать обе связи. Эти правила могут быть скомбинированы. Например:

Это означает что слово должно содержать либо связь типа «A» справа, либо связь типа «B» слева и связь типа «С» справа. Другие комбинации будут некорректны.

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

Некоторые раземы опциональны, для этого используются фигурные скобки. Например:

Это означает что слово должно содержать связь типа «А» справа, и оно может содержать связь типа «В» справа, но не обязано содержать её. Фигурные скобки могут также заключать в себе сложные выражения, например:

Эквивалентный способ записи опционального выражения «» следующий: «(X- or ())».

Слово может также создавать неопределенное число связей одного типа с другими словами. Для этого, используется multi-connector символ «@». Например, в следующем примере слово может создавать любое число связей типа F со словами справа (но не обязано содержать их).

(Если слово имеет «@A+», без фигурных скобок, то оно обязано содержать как минимум одну связь типа A (справа), остальные опциональны). Порядок элементов в выражении (connector expression) важен. Он диктует относительную близость (relative closeness) слов, которые будут соединены.

В этом примере слово «blah» должно образовывать связь типа «А» справа и связь типа «B» справа, и слово, образующее связь типа «А» должно быть ближе, чем слово образующее связь типа «В».

Однако, это относится только к соединениям одной направленности. Для разъемов, указывающих в противоположных направлениях, порядок не важен. Поэтому,

означает то же самое, что и:

В этом отношении:

означает то же самое, что:

Для выражений с оператором «or», таких как «A+ or B+», порядок элементов не важен.

Запись в словаре поэтому содержит слово, последующее двоеточие, а затем выражение связей (connector expression), заканчивающееся точкой с запятой. Словарь содержит серию таких записей. Любое число слов может быть помещено в список, разделенный пробелами, и все они будут обладать требованиями на связи *linking requirement):

Имя раъема (connector name) должно содержать одну или несколько заглавных букв (может быть использовано их любое число), с последующими «+» или «-«.

Также следует упомять концепцию «разъединителей» (disjunct). Разъединитель — это набор типов разъемов (connector types), образующих корректное использование слова. Выражение в словаре для любого слова может быть представлено как набор разъединителей (set of disjuncts).

Если, например, слово имеет следующее выражение:

тогда, оно имеет следующие четыре разъединителя:

Эти разъединители отображают все корректные использования слова «blah». Использование C- и A+ — корректно для слова, в то время как использование A+ и B+ некорректно. Разделители играют важную роль во внутренней работе парсера связей.

Глобальные правила (Global rules)

Также как и правила слов («word rules»), которые указаны в словаре, есть два других глобальных правила, которые контролируют, как слова могут быть соединены.

Прежде всего, ссылки не могут пересекаться. Например, следующий способ соединения четырех слов ( соединение «cat» к «dog» и «horse» к «fish») будет неправильным. Парсер просто не найдет таких связей.

Это правило планарности («planarity rule» или «crossing-links»). Во вторых, все слова в предложении должны быть косвенно связаны (indirectly connected) с каждым другим словом. Поэтому следующий путь соединения этих четырех слов также будет некорректным:

Это правило вовлеченности («connectivity» rule). Поэтому, корректное предложение — это предлоежение, которое может быть связано следующими связями:

  • все используемые слова предложении, удовлетворяют правилам связей (linking requirements);
  • не нарушаются правила планарности (crossing-links) и вовлеченности (connectivity).

Грамматика связей и её отношения с другими системами

Структура, назначенная предложению грамматикой связей значительно отличается от других грамматических систем (хотя она связана с грамматикой зависимостей). Вместо того, чтобы размышлять в терминах синтаксических функций (как субъект и объект), или составляющих (например, «глагольная составляющая»), необходимо размышлять в терминах взаимоотношений между парами слов. В предложении ниже, например, есть «S»-отношение (субъект) между «dog» и «has»; отношение «PP» (past-participle) между «has» и «gone»; и «D»-отношение (determiner) между «the» и «dog:

Однако, можно заметить, что части речи, синтаксические функции и составляющие могут быть восстановлены из структуры связей (link structure) довольно просто.

Основы теории формальных грамматик

Глава 1. ЯЗЫКИ И ГРАММАТИКИ. ОБОЗНАЧЕНИЯ, ОПРЕДЕЛЕНИЯ И КЛАССИФИКАЦИЯ………………………………………………………………………………6

1.1. Понятие грамматики языка. Обозначения……………………………………………7

1.2. Классификация грамматик по Хомскому………………………..…………………13

1.3. Техника построения КС- и А- грамматик…………………………………………..16

1.4. Синтаксические деревья вывода в КС-грамматиках. Представление

А-грамматик в виде графа состояний. Неоднозначность грамматик……………..19

1.5. Синтаксический анализ А-языков…………………………………………………..23

Глава 2. РАСПОЗНАВАТЕЛИ И АВТОМАТЫ.……………………………….….…………32

Глава 3. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ…………….35

3.1. Автоматные грамматики и конечные автоматы…………………………………….35

3.2.Эквивалентность недетерминированных и детерминированных А-грамматик…… 36

Глава 4. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КОНТЕКСТНО-СВОБОДНЫХ

4.1. Декомпозиция правил грамматики…………………………………………………. 42

4.2. Исключение тупиковых правил из грамматик………………………………………46

4.3. Обобщенные КС-грамматики и приведение грамматик к удлиняющей форме…….48

4.4. Устранение левой рекурсии и левая факторизация………………………………..…52

Глава 5. СВОЙСТВА АВТОМАТНЫХ И КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ…55

5.1. Общий вид цепочек А-языков и КС-языков………………………………………..55

5.4. Неоднозначность КС-грамматик и языков…………………………………………71

Глава 6. СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-языков……………………………. ……. 75

6.1. Методы анализа КС-языков. Грамматики предшествования………………….…75

6.2. Грамматики предшествования Вирта……………………………………………. 77

Грамматики предшествования Флойда…….……………………………………. 79

7.1. Польская инверсная запись….……………………………………………………. 85

7.3. Генерирование команд по ПОЛИЗу………………………………….…………. 89

7.4. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ………..……….91

Глава 8. ОСНОВНЫЕ ФАЗЫ КОМПИЛЯЦИИ……………………………………. ……100

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ…………………………………………114

Лингвистика — наука о языке. Математическая лингвистика — наука, занимающаяся формальными методами построения и изучения языков.

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

Импульсом к созданию и совершенствованию этой теории послужило развитие вычислительной техники и, как следствие, необходимость в средствах общения человека с ЭВМ. Во всех применениях ЭВМ должна понимать какой-либо язык, на котором пользователь может сообщить ей алгоритмы решения задач и исходные данные. Каждая ЭВМ имеет собственный язык машинных команд, представляемых в двоичном коде и отражающих отдельные операции процессора. На первых этапах развития вычислительной техники программисты общались с ЭВМ именно на этом примитивном языке, но человек не способен хорошо мыслить в категориях цифрового языка машины. Автоматизация программирования привела к созданию вначале языков ассемблера, а затем и алгоритмических языков высокого уровня, перевод с которых на родной машинный язык был поручен самой ЭВМ. Программы такого перевода называются трансляторами.

С проблемами объяснения языка машине сталкиваются многие разработчики программного обеспечения. Человеку свойственно изобретать новые языки. Здесь речь может идти не только о сложных компиляторах для новых алгоритмических языков программирования. Любая автоматизированная система должна понимать некоторый входной язык запросов. Новые информационные технологии предполагают привлечение конечного пользователя (ученого, конструктора, технолога, оператора) — специалиста в конкретной области, а не в области вычислительной техники и технологии программирования, к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс: пользователь должен ставить задачи и получать результаты их решения в терминах известной ему предметной области. То есть, необходима разработка широкого спектра предметно-ориентированных языков. Специалист в области программного обеспечения должен знать, как создаются языки и их программная поддержка.

Чтобы объяснить язык машине, необходимо четко представлять, как он устроен и как мы его понимаем. Задумавшись над этим, мы увидим, что не знаем, как мы понимаем наш родной язык. Процесс этого понимания подсознателен, интуитивен. Но чтобы создать транслятор, необходимо иметь алгоритм перевода текста в те действия, которые этот текст требует выполнить, а это, в свою очередь, требует формализации языка. Задачи формализации языка и решает математическая лингвистика. Естественные языки слишком сложны, и формализовать их полностью пока не удается. Алгоритмические языки, напротив, уже создаются в расчете на формализацию. Теория формальных языков — это наиболее развитая ветвь математической лингвистики, представляющая по сути методику объяснения языка машине. Прежде чем рассматривать определения, модели и методы этой теории, рассмотрим некоторые понятия на примерах из естественных языков.

Язык – это множество предложений (фраз), построенных по определенным правилам.

Грамматика— свод правил, определяющих принадлежность фразы языку.

Любой язык должен удовлетворять свойствам разрешимости и однозначности.

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

Основными разделами грамматики являются синтаксис и семантика.

Синтаксис— свод правил, определяющих правильность построения предложений языка.

Семантика — свод правил, определяющих семантическую или смысловую правильность предложений языка.

Предложение может быть синтаксически верным и семантически неверным.

Синтаксис обычно упрощается тем, что не все фразы языка обязаны иметь смысл. Зачастую трудно понять смысл футуристов или речь некоторых политиков. В этой связи интересен пример академика Л.В.Щербы: «Глокая куздра штеко будланула бокра и кудрячит бокренка». Это фраза на русском языке, так как её можно разобрать по членам предложения, но смысл её неясен.

Синтаксический анализ фразы можно записать в виде дерева грамматического разбора. Узлы дерева, такие как подлежащее, сказуемое, группа подлежащего, предложение соответствует синтаксическим понятиям, а листья – это слова, из которых строится предложение. Обрубив в дереве часть листьев и ветвей, мы получим сентенциальную форму (выводимую цепочку).

Илон Маск рекомендует:  Что такое код ibase_blob_cancel
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL