Regular vs Context Free Grammars

Question

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

Итак, если мы думаем о pumping lemma for regular languages, то, что он говорит, является то, что любой регулярный язык может быть разбит на три части, х, у и г, где все экземпляры языка находятся в ху * г (где * Клини повторение, то есть 0 или больше копий и.) У вас в основном есть один «нетерминальный», который можно развернуть.

Теперь, что относительно контекстно-свободных языков? Там в аналогичный pumping lemma for context-free languages, который разбивает строки в языке на пять частей, uvxyz, и где все экземпляры языка в уф ^я ху ^я г, ибо я ≥ 0. Теперь, у вас есть два «nonterminals», которые могут быть воспроизведены или перекачаны, , если у вас есть тот же номер.

Answer 3

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

Answer 4

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

Answer 5

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

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

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

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

Answer 6

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

Answer 7

Регулярной грамматика: - грамматика, содержащее производство следующим является РГ:

V->TV or VT 
V->T 

, где V = переменные и Т = терминал

РГ может быть оставлена ​​Линейной грамматика или правый Liner грамматика, но не Средняя линейная грамматика.

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

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

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

Неоднозначность Грамматика: - для строки х их существует более одного 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 8

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

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

● а

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

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

● ABC

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

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

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

1. A → A, где А представляет собой нетерминальное в N, и представляет собой терминал в Й
2. а → в где а и в находятся в N, и в Й
3. A → & epsi; где а в N и & epsi; является пустой строкой

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

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

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

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