Рубрики

Неоднозначность в контекстно-свободной грамматике и контекстно-свободных языках

Прежде чем читать эту статью, мы рекомендуем вам сначала прочитать об автоматах Pushdown и Context Free Languages .

Предположим, у нас есть не зависящая от контекста грамматика G с правилами производства: S -> aSb | bSa | СС | е

Самый левый вывод (LMD) и дерево деривации: крайний левый вывод строки из начального символа S выполняется путем замены крайнего левого нетерминального символа на RHS соответствующего производственного правила. Например, крайний левый вывод строки abab из приведенной выше грамматики G выполняется следующим образом:
S => a S b => ab S ab => abab
Подчеркнутые символы заменяются с использованием правил производства.

Дерево деривации: оно говорит о том, как строка получена с использованием правил производства из S и показана на рисунке 1.

Самый правый вывод (RMD): крайний правый вывод строки из начального символа S выполняется путем замены крайнего правого нетерминального символа на RHS соответствующего производственного правила. например; Самый правый вывод строки abab из приведенной выше грамматики G выполняется следующим образом:
S => S S => Sa S b => S ab => a S bab => abab
Подчеркнутые символы заменяются с использованием правил производства. Дерево деривации для abab с использованием самого правого деривации показано на рисунке 2.

Деривация может быть либо LMD, либо RMD, либо и тем, и другим. Например, S => a S b => ab S ab => abab — это LMD, а также RMD, но S => S S => Sa S b => S ab => a S bab => abab — это RMD, но не LMD.

Неопределенная контекстная грамматика: не зависящая от контекста грамматика называется неоднозначной, если для строки, генерируемой грамматикой, существует более одного LMD или более одного RMD. Также будет более одного дерева деривации для строки в неоднозначной грамматике. Описанная выше грамматика неоднозначна, поскольку существует два деривационных дерева (рисунок 1 и рисунок 2). Для строки abab может быть несколько RMD:
S => S S => Sa S b => S ab => a S bab => abab
S => a S b => ab S ab => abab

Неоднозначные языки без контекста: язык без контекста называется неоднозначным, если нет однозначной грамматики для определения этого языка, и его также называют неотъемлемо неоднозначным языком без контекста.
eg- L = {a n b n c m } U {a n b m c m }

Замечания :

  • Если не зависящая от контекста грамматика G неоднозначна, язык, сгенерированный грамматикой L (G), может быть или не быть неоднозначным.
  • Не всегда возможно преобразовать неоднозначный CFG в однозначный CFG. Только некоторые неоднозначные CFG могут быть преобразованы в однозначные CFG.
  • Не существует алгоритма для преобразования неоднозначного CFG в однозначный CFG.
  • Всегда существует однозначный CFG, соответствующий однозначному CFL.
  • Детерминированные CFL всегда однозначны и анализируются парсерами LR.

Вопрос: рассмотрим следующие утверждения о контекстно-свободной грамматике
G = {S -> SS, S -> ab, S -> ba, S ->?}
И.Г неоднозначен
II. G производит все строки с одинаковым количеством а и б
III. G может быть принят детерминированным КПК

Какая комбинация ниже выражает все истинные утверждения о G?
Только я
B. только I и III
C. II и III только
D. I, II и III

Решение: Существуют разные LMD для строки abab, которые могут быть
S => S S => S SS => ab S S => abab S => abab
S => S S => ab S => abab
Так что грамматика неоднозначна. Поэтому утверждение я верно.

Утверждение II гласит, что грамматика G производит все строки с одинаковым числом a и b, но не может генерировать строку aabb. Так что утверждение II неверно.
Утверждение III также является правильным, поскольку оно может быть принято детерминистическим КПК. Так что правильный вариант (B).

Вопрос: Какое из следующих утверждений ЛОЖНО?
О. Существуют языки без контекста, так что все генерирующие их грамматики без контекста неоднозначны.
Б. Однозначная контекстно-свободная грамматика всегда имеет уникальное дерево разбора для каждой строки сгенерированного ею языка.
C. Как детерминированные, так и недетерминированные автоматы нажатия всегда принимают один и тот же набор языков.
D. Конечный набор строк из одного алфавита всегда является обычным языком.

Решение: (A) правильно, потому что для неоднозначных CFL все соответствующие ему CFG неоднозначны.
(B) также правильно, так как однозначный CFG имеет уникальное дерево разбора для каждой строки сгенерированного им языка.
(C) является ложным, поскольку некоторые языки принимаются недетерминированным PDA, но не детерминированным PDA.
(D) также верно, поскольку конечное множество строк всегда регулярно.
Таким образом, вариант (C) является правильным вариантом.

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

Эта статья предоставлена Sonal Tuteja .

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

Рекомендуемые посты:

Неоднозначность в контекстно-свободной грамматике и контекстно-свободных языках

0.00 (0%) 0 votes