Я понимаю следующие утверждения, чтобы быть правдой:
- Два разных вывода строки в данном CFG могут иногда приписывать строку одному и тому же дереву разбора.
- Когда есть производные некоторой строки в данном CFG, которые приписывают различные деревья разбора, CFG является неоднозначным.
- Некоторые языки без контекста, генерируемые неоднозначными CFG, также генерируются однозначными CFG.
- Некоторые языки таковы, что единственные CFG, которые могут их генерировать (а таких есть), неоднозначны.
Q1. Я понимаю также, что неразрешимо, является ли произвольный CFG неоднозначным, в смысле пункта 3 выше. Или, скорее, неразрешимо, является ли язык без контекста неоднозначным в смысле пункта 4? Или оба неразрешимы?
Q2. Какие из пунктов 1-4 становятся ложными, когда мы заменяем «контекстно-свободный» на «обычный»? Регулярные грамматики и языки всегда однозначны?
fl.formal-languages
regular-language
context-free
dubiousjim
источник
источник
Ответы:
О вопросе 1: и проблема неоднозначности (с учетом CFG, является ли она неоднозначной) и проблема внутренней неоднозначности (с учетом CFG, является ли ее язык по своей сути неоднозначным, т.е. является ли любой эквивалентный CFG неоднозначным) неразрешимы. Вот оригинальные ссылки:
О Q2: Регулярная грамматика - это «односторонняя линейная» контекстно-свободная грамматика, где не более одного нетерминала появляется в правой части любого правила, и где этот нетерминал находится в конце (в правильных линейных грамматиках) или в первом (в левые линейные грамматики) положение. Такие грамматики легко переводятся в эквивалентные конечные автоматы (грубо говоря, рассматривая каждый нетерминал как состояние), которые однозначны, если регулярная грамматика однозначна. Класс однозначных регулярных грамматик и однозначных автоматов был изучен, в частности, Stearns and Hunt (1985) , которые показывают, что им нравятся алгоритмы для решения задачи включения.
О связи между деривациями (т. Е. Последовательностями приложений правил где - это правило грамматики) и деревьями деривации (т. Е. Когда узел с меткой является родителем последовательности узлов , где - это правило): в общем CFG могут быть разные деривации, которые по-разному посещают одно и то же дерево дериваций.A → α A X 1 , … , X m A → X 1 ⋯ X mβA γ⇒ βα γ A → α A Икс1, … , Xм A → X1⋯ Xм
Эти различные деривации происходят потому, что у одного есть выбор между применением правила грамматики в двух разных местах в форме предложения: в форме предложения по крайней мере с двумя нетерминалами и , можно применить сначала и получите , или сначала и получите , но применение другого правила приведет к тому же . Наложение самого левого (всегда выводит самый левый нетерминал в любой форме предложения) или самое правоеВ → & alpha ; & gamma & alpha ; п В & thetas ; B → & beta ; & gamma п & beta ; & thetas ; & gamma & alpha ; п & beta ; & thetas ;γA ηB θ A В A → α γα ηB θ B → β γA ηβθ γα ηβθ деривации устанавливают фиксированный порядок посещения деревьев деривации, и затем для данного деривационного дерева существует один деривация.
В линейной контекстно-свободной грамматике такого выбора нет, так как в любой предложенной форме существует не более одного нетерминала, и для данного дерева деривации существует только один вывод, который является как крайним левым, так и самым правым.
Наличие двух разных деревьев разбора с одинаковым выходом (последовательность листьев) является определением того, что является неоднозначным, оно не меняется при рассмотрении регулярных грамматик. В качестве альтернативы можно также запросить два разных крайних левых вывода. Обратите внимание, что деривация в односторонней грамматике соответствует принимающему прогону в связанном с ним автомате конечных состояний, который точно так же называется неоднозначным : когда существуют два разных приемных прогона для данного входа .w wвес вес вес
и 4. Если вы берете представление о автоматах в конечном состоянии, достаточно определить ваш неоднозначный автомат, чтобы получить однозначный автомат для того же языка: для любого данного слова будет один прогон. Этот детерминированный автомат эквивалентен однозначной регулярной грамматике.
Чтобы ответить на ваш комментарий: существуют неоднозначные регулярные грамматики, например, имеет два крайних левых вывода для : и . Эквивалентной однозначной грамматикой является .a S ⇒ A ⇒ a S ⇒ B ⇒ a S → aS→ A ∣ B ,А → а ,B → a a S⇒ A ⇒ a S⇒ B ⇒ a S→ а
Относительно связи с Q1: решаемо, является ли регулярная грамматика неоднозначной (присущая проблема неоднозначности не очень сложна для регулярных грамматик, поскольку ответ всегда «нет», даже не глядя на входную грамматику). Это можно проверить в с помощью возведения в квадрат на его ассоциированном автомате: построить произведение автомата на себя и посмотреть, доступно ли какое-либо состояние с и совместный доступ. Самое старое упоминание об этой идее - статья Эвена (1965) .( q , q ′ ) q ≠ q ′O(|G|2) ( д, д') Q≠ д'
источник
Q1. Все неразрешимо, так как вопрос о том, производит ли грамматика язык (содержащий все слова) или нет, неразрешим. Но если у вас есть какая-то определенная грамматика, например, грамматика, построенная с помощью детерминированного КПК, вопросы можно решить, но это очень скучный случай.Σ ∗грамм Σ*
Я не совсем понял, о каких языках вы говорите в 4. Каждый CF-язык имеет неоднозначную грамматику.
Q2. Все решаемо, если вы имеете дело с обычной грамматикой. Вам просто нужно создать минимальный DFA, и используя его, вы можете создать однозначную грамматику. Если вы имеете дело с обычным языком, определенным грамматикой CF, ответ - нет - см. Q1.
источник
Это зависит от того, заменяете ли вы «свободный от контекста» словом «обычный» только перед «языком (языками)» или перед «грамматикой (ями)».
Все регулярные языки генерируются регулярными грамматиками и, в частности, однозначными регулярными грамматиками, например, правильными правильными грамматиками LL (1) , которые все однозначны.
источник