Вопросы о формальных грамматиках, порождающие описания формальных языков.
Люди часто говорят, что парсеры LR (k) более мощные, чем парсеры LL (k) . Эти заявления в большинстве случаев расплывчаты; в частности, следует ли сравнивать классы для фиксированного или объединения по всем ? Так как на самом деле ситуация? В частности, меня интересует, как вписывается LL...
Давайте назовем контекстно-свободный язык детерминированным тогда и только тогда, когда он может быть принят детерминированным автоматом, и недетерминированным в противном случае. Давайте назовем контекстно-свободный язык по своей сути неоднозначным тогда и только тогда, когда все...
Видя, что в иерархии Хомского языки типа 3 могут распознаваться конечным автоматом без внешней памяти (т. Е. Конечным автоматом), тип 2 - конечным автоматом с одним стеком (т. Е. Автоматом с понижением) и тип 0 - конечный автомат с двумя стеками (или, что эквивалентно, лента, как в случае с...
В Интернете есть много определений о том, что такое контекстно-свободная грамматика, но ничего, что я нахожу, не удовлетворяет мою основную проблему: В каком контексте он свободен? Чтобы исследовать, я погуглил «контекстно-зависимую грамматику», но мне так и не удалось найти смысл «контекста»....
Некоторое время я изучал компиляторы и искал, что означает «контекст» в грамматике и что означает, что грамматика должна быть «контекстно-свободной», но безрезультатно. Так может кто-нибудь помочь с...
У меня есть набор пар. Каждая пара имеет форму (x, y), так что x, y принадлежат целым числам из диапазона [0,n). Итак, если n равно 4, то у меня есть следующие пары: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) У меня уже есть пары. Теперь я должен построить комбинацию, используя n/2пары, чтобы ни одно из...
Есть много способов доказать, что язык не является контекстно-свободным, но как мне доказать, что язык не является контекстно-независимым? Какие методы существуют, чтобы доказать это? Очевидно, один из способов - показать контекстную грамматику для языка. Существуют ли какие-либо систематические...
Моя проблема в том, как я могу доказать, что грамматика однозначна? У меня есть следующие грамматики: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression...
EPAL, язык четных палиндромов, определяется как язык, генерируемый следующей однозначной контекстно-свободной грамматикой: S→aaS→aaS \rightarrow a a S→bbS→bbS \rightarrow b b S→aSaS→aSaS \rightarrow a S a S→bSbS→bSbS \rightarrow b S b EPAL - это «проклятие» многих алгоритмов синтаксического...
Задание формальных языков с помощью формальных грамматик является частой задачей: нам нужны грамматики не только для описания языков, но также для их анализа или даже для правильной науки . Во всех случаях важно, чтобы грамматика под рукой была правильной , то есть генерировала именно нужные слова....
Этот вопрос был перенесен из теоретического обмена стеков информатики, поскольку на него можно ответить в обмене стеков информатики. Мигрировал 7 лет назад . Я ищу математические теории, которые имеют дело с описанием формальных языков (набор строк) в целом, а не только грамматических...
В дизайне компилятора, почему левая рекурсия должна быть исключена в грамматике? Я читаю, что это потому, что это может вызвать бесконечную рекурсию, но разве это не так и для правильной рекурсивной...
Давайте рассмотрим две не зависящие от контекста грамматики и G 2 и зададим следующий вопрос: Являются ли L ( G 1 ) = L ( G 2 ) , то есть эквивалентны ли эти две грамматики?грамм1грамм1G_1грамм2грамм2G_2L ( G1) = L ( G2)L(грамм1)знак равноL(грамм2)L(G_1) = L(G_2) В общем, эта проблема неразрешима....
Согласно этой статье в Википедии , неограниченные грамматики эквивалентны машинам Тьюринга. В статье отмечается, что я могу преобразовать любую машину Тьюринга в неограниченную грамматику, но она показывает только, как преобразовать грамматику в машину Тьюринга. Как мне действительно это сделать и...
Может ли контекстно-свободная грамматика включать «мертвые состояния» из автомата, такие как G = ( { a , b , c } , { A , B , C} , { A → a B , B → b , B → C, C→с C} , A )?граммзнак равно({a,б,с},{A,В,С},{A→aВ,В→б,В→С,С→сС},A)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\},...
Если у меня есть грамматика типа 3, она может быть представлена в автомате (без каких-либо операций со стеком), поэтому я могу представлять регулярные выражения с использованием контекстно-свободных языков. Но могу ли я знать, что грамматика типа 3 - это , L L ( 1 ) , S L R ( 1 ) и т. Д. Без...
Говорят, что пересечение языка L, не зависящего от контекста, с обычным языком M всегда является контекстно-свободным. Я понял доказательство создания перекрестного продукта, но до сих пор не понимаю, почему он не контекстный, а не регулярный. Язык, генерируемый таким пересечением, имеет строки,...
Можно утверждать, что большинство языков, созданных для описания повседневных проблем, являются контекстно-зависимыми. С другой стороны, возможно и нетрудно найти некоторые языки, которые не являются рекурсивными или даже не рекурсивно-перечислимыми. Между этими двумя типами находятся рекурсивные,...
Определим язык LLL как L = { a , b } ∗ - { w w ∣ w ∈ { a , b } ∗ }L={a,b}∗−{ww∣w∈{a,b}∗}L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\} . Другими словами, LLL содержит слова, которые не могут быть выражены как какое-то слово, повторенное дважды. Является ли LLL контекстно-свободный или нет? Я пытался...
Согласно статье в Википедии , L в означает «сканирование слева направо», а «R» означает «крайний правый вывод». Однако в оригинальной статье Кнута по грамматике L R ( k ) он определяет язык L R ( k ) (на стр. 610) как язык, который «переводим слева направо с ограничением k ».L R (k )Lр(К)LR(k)L R (...