Описание тега context-free-language

Вопросы с тегом
В формальной теории языков контекстно-свободный язык (CFL) - это язык, порожденный некоторой контекстно-свободной грамматикой (CFG). Набор обычных языков - это подмножество набора контекстно-свободных языков.
1 ответ

Генерация CFG для языка

Рассмотреть язык {anbmcp | n <= p OR m <= p} создать CFG для этого языка.Я начал это с S -> aA | aB, но я не уверен, как мне поступить при определении A или B. "ИЛИ" кажется довольно сложным для включения в определение языка, так как нет необх…
04 ноя '15 в 17:32
1 ответ

Алгоритм проверки грамматики против другой грамматики в ll(1)

Мне нужен алгоритм, который проверяет, является ли язык G1 подмножеством языка G2 или нет. (Предположим, что G1 и G2 - две грамматики LL(1) с одинаковыми алфавитами, правила производства которых имеют форму A -> aB или A -> a, а "a" не является эпси…
20 дек '15 в 17:10
1 ответ

Построить грамматику для языка

У меня есть вопрос по этому вопросу: L = пусто, где алфавит {a,b} как создать грамматику для этого? как может быть производственное правило? заранее спасибо
04 май '17 в 12:41
1 ответ

Определение не зависящего от контекста грамматики для конкретного языка

У меня есть язык, в котором каждая строка в этом языке имеет четное количество 0 как 1 (например, 0101, 1010, 1100, 0011, 10 все на языке). Я надеялся определить грамматику без контекста, которая описывает этот язык. После определения грамматики без…
17 мар '14 в 21:12
1 ответ

Однозначная контекстно-бесплатная грамматика

Я читал контекстную грамматику и столкнулся с неоднозначной грамматикой. Если язык, созданный CFG, имеет более 1 дерева разбора, то CFG является неоднозначной грамматикой. Есть ли способ, которым я могу узнать или доказать, что грамматика однозначна…
02 фев '14 в 06:11
1 ответ

Нужна помощь в создании CFG для языка

Я хочу сопоставить строки, которые содержат "k" число 0, а затем "k+4" число 1, где k больше или равно нулю Я пробовал следующую грамматику это правильно? S->0S1|1111
24 сен '16 в 22:38
1 ответ

Построение линейной грамматики для языка

Я нахожу трудности в построении грамматики для языка, особенно с линейной грамматикой. Может ли кто-нибудь дать мне несколько основных советов / методологий, где я могу построить грамматику для любого языка? заранее спасибо У меня есть сомнения, пра…
04 май '17 в 09:44
1 ответ

Этот язык регулярный или нет?

У меня есть язык {4^(w⋅g)34^(g)|w,g∈NAT} над алфавитом {0,1}. Мне нужно выяснить, является ли этот язык узнаваемым, разрешимым, контекстно-зависимым, регулярным или ни одного из них. Как мне поступить так или узнать? Спасибо
30 июл '14 в 10:18
1 ответ

Является ли язык описания регулярных выражений регулярным сам по себе?

Если мы опишем регулярные выражения с операторами *, | и конкатенация . (который мы просто опускаем для ясности) и скобки (, ) и несколько букв из какого-то алфавита SigmaТогда язык, который описывает регулярные выражения, сам по себе регулярный? На…
12 май '14 в 00:44
1 ответ

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

У меня проблемы с приближением к следующей проблеме. Дайте контекстно-свободную грамматику для следующего языка: {x#y | x,y in {0,1}* and |x| != |y|} Как лучше всего подойти к этому вопросу? Сейчас я просто использую интуицию для решения подобных во…
26 апр '15 в 10:26
1 ответ

Решение шутки, связанной с EBNF

Как вы думаете, каково решение следующей проблемы, связанной с EBNF? Следующее сообщение было замечено на наклейке на бампере: Воняет Синтаксис. В чем шутка? Пока что это мне пришло в голову: r1 ::= in | yn r2 ::= ks | x Stinks Syntax ::= St r1 r2 |…
14 мар '16 в 16:30
2 ответа

Найти грамматику двоичного числа, делимого на 5 с 1 как MSB

Как я могу найти грамматику двоичного числа, делимого на 5 с 1 как MSB и найти обращение L Итак, мне нужна грамматика, которая генерирует числа, как.. 5 = 101 10 = 1010 15 = 1111 20 = 10100 25 = 110011 и так далее
14 июн '14 в 11:27
1 ответ

Как я могу сказать, что язык не зависит от контекста с первого взгляда?

Мой профессор ожидает, что мы быстро узнаем, является ли данный язык регулярным, контекстно-свободным, но не регулярным, или не контекстно-свободным (другими словами, без рисования КПК, написания контекстно-свободной грамматики и использования накач…
18 ноя '16 в 03:08
2 ответа

Понимание основ CFG

Вы только что начали главу о КЛЛ в книге Сипсера и уже не понимаете основ. Пусть это будет грамматика некоторого языка: S -> A0A A -> 00A | 11A | 10A | 01A | e Я действительно запутался в этой части A0A. Означает ли это, что левая сторона от 0…
14 май '16 в 21:04
2 ответа

Союз детерминированного контекста Свободный язык и обычный язык Результаты?

Данный L1 является детерминированным контекстно-свободным языком, а L2 является обычным языком L1 U L2 результаты DCFL или обычные? приведите несколько примеров с контекстом
11 янв '15 в 07:16
0 ответов

{a^nb^n} union {a } является детерминированным или нет

Я запутался, по моему мнению, это не должно быть детерминированным, поскольку будут состояния для (a,zo/azo) перехода в q1 и (a,z0/eplison) перехода в конечное состояние. Это правда или нет
01 май '16 в 18:32
1 ответ

L = { 1 ^ n (n+1) / 2 } не зависит от контекста?

Я заметил, что язык L генерирует слова с длиной, которая представляет числа треугольника: 1,3,6,10,15 и т. Д. Я пытаюсь использовать лемму Пемпингта для w=1^(p(p+1), но я нигде не доходил.. Может кто-нибудь помочь или дать мне представление, как это…
29 окт '17 в 17:13
1 ответ

Как написать CFG с функциями?

В задании меня попросили написать CFG для таких функций, как: def f (x, y): вернуть x + y def g (x, y): вернуть x - y def h (x, y, z): вернуть x + y % z def w (x, y, z): вернуть x * y - z а также def h1(x, y, z): возврат (x + y)% z def h2 (x, y, z):…
31 окт '15 в 00:56
1 ответ

Детерминированная контекстно-свободная грамматика против контекстно-свободной грамматики?

Я читаю свои заметки для моего класса сравнительных языков, и я немного запутался... В чем разница между контекстно-свободной грамматикой и детерминированной контекстно-свободной грамматикой? Я специально читаю о том, как парсеры O(n^3) для CFG и ко…
20 мар '14 в 02:18
2 ответа

Алгоритм преобразования нормальных форм Хомского

Почему мы добавляем новое начальное состояние S0 -> S, когда хотим преобразовать грамматику в нормальную форму Хомского? Что пойдет не так, если мы этого не сделаем? Сначала я думал, что это из-за правил эпсилон. Но мы не удаляем эпсилон-правило из …
31 май '16 в 22:57