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

Question

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

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

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

Может кто-нибудь помочь мне собрать все это вместе?

Answer 1

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

Так, например, для палиндрома он имеет вид

S->ABA
A->something
B->something

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

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

Answer 2

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

Итак, если мы подумаем о лемме прокачки для регулярных языков , то, по сути, говорится, что любой регулярный язык можно разбить на три части: x , y и z , где все экземпляры языка находятся в xy * z (где * - повторение Клини, т. Е. 0 или более копий у .) У вас в основном есть один «нетерминал», который можно расширить.

А как насчет контекстно-свободных языков? Существует аналогичная прокачка леммы для контекстно-свободных языков , которая разбивает строки в языке на пять частей, uvxyz , и где все экземпляры языка находятся в uv ⁱ xy ⁱ z , для i & ge; 0. Теперь у вас есть два"нетерминалов", которые можно копировать или перекачивать, , если у вас есть такое же число .

Answer 3

Разница между обычной и контекстно-свободной грамматикой: (N, Σ, P, S): терминалы, нетерминалы, производственные процессы, начальное состояние. Терминальные символы

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

● abc

Нетерминальные символы (или синтаксические переменные)

● заменено группами терминальных символов в соответствии с правилами производства

● ABC

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

1. B → a, где B - нетерминал в N, а a - терминал в Σ
2. B → aC, где B и C в N, а a в Σ
3. B → ε, где B находится в N, а ε обозначает пустую строку, то есть строку длиной 0

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

1. A → a, где A - нетерминал в N, а a - терминал в Σ
2. A → Ba, где A и B в N, а a в Σ
3. A → ε, где A в N, а ε - пустая строка

контекстно-бесплатная грамматика (CFG)

○ формальная грамматика, в которой каждое производственное правило имеет форму V → w

○ V - один нетерминальный символ

○ w - строка терминалов и / или нетерминалов (w может быть пустым)

Answer 4

Регулярные выражения

• Основы лексического анализа
• Представлять обычные языки

Грамматики без контекста

• Основа синтаксического анализа
• Представляет языковые конструкции

Answer 5

Обычная грамматика: - грамматика, содержащая следующую продукцию: RG:

V->TV or VT
V->T

где V = переменная и T = клемма

RG может быть левой линейной грамматикой или правой линейной грамматикой, но не средней линейной грамматикой.

Как мы знаем, все RG являются линейной грамматикой, но RG - только левая или правая линейная грамматика.

Обычная грамматика может быть неоднозначной.

S->aA|aB
A->a
B->a

Неоднозначная грамматика: - для строки x их существует более одного LMD или более RMD или более одного дерева синтаксического анализа или одного LMD и одного RMD, но оба создают различное дерево синтаксического анализа.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

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

CFG: - Грамматика называется CFG, если ее Производство находится в форме:

   V->@   where @ belongs to (V+T)*

DCFL: - поскольку мы знаем, что все DCFL - это грамматика LL (1), а все LL (1) - это LR (1), поэтому она никогда не будет неоднозначной. поэтому DCFG никогда не будет двусмысленным.

Мы также знаем, что все RL являются DCFL, поэтому RL никогда не будет двусмысленным. Обратите внимание, что RG может быть неоднозначным, но RL нет.

CFL: CFl Может или не может быть двусмысленным.

Примечание: RL никогда не будет по своей сути неоднозначным.

Answer 6

Грамматика не зависит от контекста, если все производственные правила имеют форму: A (то есть левая сторона правила может быть только одной переменной; правая сторона не ограничена и может быть любой последовательностью терминалов и переменных) , Мы можем определить грамматику как 4-кортеж, где V - конечное множество (переменные), _ - конечное множество (терминалы), S - начальная переменная, а R - конечный набор правил, каждое из которых является отображением V * +1001 * обычная грамматика является либо правой, либо левой линейной, тогда как грамматика без контекста в основном представляет собой любую комбинацию терминалов и нетерминалов. следовательно, мы можем сказать, что регулярная грамматика является подмножеством контекстно-свободной грамматики. После этих свойств можно сказать, что набор Context Free Languages ​​также содержит набор Regular Languages ​​

Answer 7

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

Answer 8

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