Бесплатные бесплатные грамматики

Ответ 1

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

● abc

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

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

● ABC

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

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

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

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

контекстная свободная грамматика (CFG)

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

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

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

Ответ 4

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

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

Контекстные бесплатные грамматики

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

Ответ 5

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

Ответ 6

Регулярная грамматика: - грамматика, содержащая производство следующим образом: 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 никогда не будет по сути неоднозначным.

Ответ 7

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

Ответ 8

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