Неоднозначность в обычных и контекстно-свободных языках

11

Я понимаю следующие утверждения, чтобы быть правдой:

  1. Два разных вывода строки в данном CFG могут иногда приписывать строку одному и тому же дереву разбора.
  2. Когда есть производные некоторой строки в данном CFG, которые приписывают различные деревья разбора, CFG является неоднозначным.
  3. Некоторые языки без контекста, генерируемые неоднозначными CFG, также генерируются однозначными CFG.
  4. Некоторые языки таковы, что единственные CFG, которые могут их генерировать (а таких есть), неоднозначны.

Q1. Я понимаю также, что неразрешимо, является ли произвольный CFG неоднозначным, в смысле пункта 3 выше. Или, скорее, неразрешимо, является ли язык без контекста неоднозначным в смысле пункта 4? Или оба неразрешимы?

Q2. Какие из пунктов 1-4 становятся ложными, когда мы заменяем «контекстно-свободный» на «обычный»? Регулярные грамматики и языки всегда однозначны?

dubiousjim
источник
Языки, которые вы упоминаете в пункте 4, «по своей сути неоднозначны». Что касается первого квартала, я думаю, что неразрешимо, является ли Грамматика двусмысленной. Таким образом, 3 и 4 неразрешимы.
Ламин
Правильно, языки пункта 4 называются «по сути неоднозначными».
Dubiousjim
4
Q1: оба неразрешимы. Q2: 1 не представляется возможным, потому что в любой фразеальной форме есть не более одного нетерминала, поэтому любой вывод является как крайним левым, так и самым правым; 2 это все еще правда; 3 остается верным, если вы удалите бит `` Также ''; 4 больше не соответствует действительности, например, определив свою грамматику, вы получите однозначную.
Сильвен
1
@Sylvain сделать это ответ?
Юваль Фильмус
@ Сильвен, спасибо, и да, ответь. Могу ли я подтвердить, что понял? re 2: То есть существует регулярная грамматика, которая может генерировать одну и ту же строку с разными деревьями разбора? (С тех пор я встречал ссылку на «неоднозначные NFA», но я не уверен, что в этом смысле я использую «ambig»). Что касается 3 и 4, я думаю, вы говорите, что некоторые регулярные языки могут быть сгенерированы неоднозначными регулярными грамматиками, но также всегда будут генерироваться и однозначной регулярной грамматикой?
dubiousjim

Ответы:

19

О вопросе 1: и проблема неоднозначности (с учетом CFG, является ли она неоднозначной) и проблема внутренней неоднозначности (с учетом CFG, является ли ее язык по своей сути неоднозначным, т.е. является ли любой эквивалентный CFG неоднозначным) неразрешимы. Вот оригинальные ссылки:


О Q2: Регулярная грамматика - это «односторонняя линейная» контекстно-свободная грамматика, где не более одного нетерминала появляется в правой части любого правила, и где этот нетерминал находится в конце (в правильных линейных грамматиках) или в первом (в левые линейные грамматики) положение. Такие грамматики легко переводятся в эквивалентные конечные автоматы (грубо говоря, рассматривая каждый нетерминал как состояние), которые однозначны, если регулярная грамматика однозначна. Класс однозначных регулярных грамматик и однозначных автоматов был изучен, в частности, Stearns and Hunt (1985) , которые показывают, что им нравятся алгоритмы для решения задачи включения.

  1. О связи между деривациями (т. Е. Последовательностями приложений правил где - это правило грамматики) и деревьями деривации (т. Е. Когда узел с меткой является родителем последовательности узлов , где - это правило): в общем CFG могут быть разные деривации, которые по-разному посещают одно и то же дерево дериваций.A α A X 1 , , X m A X 1X mβAγβαγAαAX1,,XmAX1Xm

    Эти различные деривации происходят потому, что у одного есть выбор между применением правила грамматики в двух разных местах в форме предложения: в форме предложения по крайней мере с двумя нетерминалами и , можно применить сначала и получите , или сначала и получите , но применение другого правила приведет к тому же . Наложение самого левого (всегда выводит самый левый нетерминал в любой форме предложения) или самое правоеВ & alpha ; & gamma & alpha ; п В & thetas ; B & beta ; & gamma п & beta ; & thetas ; & gamma & alpha ; п & beta ; & thetas ;γAηBθABAαγαηBθBβγAηβθγαηβθ деривации устанавливают фиксированный порядок посещения деревьев деривации, и затем для данного деривационного дерева существует один деривация.

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

  2. Наличие двух разных деревьев разбора с одинаковым выходом (последовательность листьев) является определением того, что является неоднозначным, оно не меняется при рассмотрении регулярных грамматик. В качестве альтернативы можно также запросить два разных крайних левых вывода. Обратите внимание, что деривация в односторонней грамматике соответствует принимающему прогону в связанном с ним автомате конечных состояний, который точно так же называется неоднозначным : когда существуют два разных приемных прогона для данного входа .w wwww

  3. и 4. Если вы берете представление о автоматах в конечном состоянии, достаточно определить ваш неоднозначный автомат, чтобы получить однозначный автомат для того же языка: для любого данного слова будет один прогон. Этот детерминированный автомат эквивалентен однозначной регулярной грамматике. 

    Чтобы ответить на ваш комментарий: существуют неоднозначные регулярные грамматики, например, имеет два крайних левых вывода для : и . Эквивалентной однозначной грамматикой является .a S A a S B a S aSAB,Aa,BaaSAaSBaSa

Относительно связи с Q1: решаемо, является ли регулярная грамматика неоднозначной (присущая проблема неоднозначности не очень сложна для регулярных грамматик, поскольку ответ всегда «нет», даже не глядя на входную грамматику). Это можно проверить в с помощью возведения в квадрат на его ассоциированном автомате: построить произведение автомата на себя и посмотреть, доступно ли какое-либо состояние с и совместный доступ. Самое старое упоминание об этой идее - статья Эвена (1965) .( q , q ) q q O(|G|2)(q,q)qq

Сильвен
источник
1

Q1. Все неразрешимо, так как вопрос о том, производит ли грамматика язык (содержащий все слова) или нет, неразрешим. Но если у вас есть какая-то определенная грамматика, например, грамматика, построенная с помощью детерминированного КПК, вопросы можно решить, но это очень скучный случай.Σ GΣ

Я не совсем понял, о каких языках вы говорите в 4. Каждый CF-язык имеет неоднозначную грамматику.

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

Александр Рубцов
источник
Спасибо, хорошие разъяснения по поводу Q2. Вопросы по обычному языку могут быть разрешены, если язык задан обычной грамматикой; но это еще не значит, что они решаемы, если язык указан CFG - это то, что вы говорите, верно? Итак, знаем ли мы, что это так, что вопросы о неясности и т. Д., Которые неразрешимы для произвольных CFG, также неразрешимы, если они ограничены теми CFG, которые генерируют обычные языки?
Dubiousjim
Не может быть, но они всегда разрешимы. Я имею в виду, когда вы имеете дело с языком, описываемым обычной грамматикой - подклассом CFG, любой вопрос, который вам нравится, разрешим. Но некоторые нерегулярные CFG могут производить обычный язык, и неразрешимо даже проверить, производит ли CFG обычный язык.
Александр Рубцов
2
@ alexandr-rubtsov "Когда вы имеете дело с языком, описываемым обычной грамматикой, любой вопрос, который вам нравится, разрешим". Это выглядит как чрезмерно оптимистичное утверждение ...
Ж.-Е.
Спасибо, я имел в виду «может быть» в своей риторической функции, а не в смысле «кто знает?»
Dubiousjim
@ J.-E.Pin Да, я должен был быть более деликатным и сказать что-то вроде «все естественные вопросы, такие как двусмысленность».
Александр Рубцов
0

Это зависит от того, заменяете ли вы «свободный от контекста» словом «обычный» только перед «языком (языками)» или перед «грамматикой (ями)».

Все регулярные языки генерируются регулярными грамматиками и, в частности, однозначными регулярными грамматиками, например, правильными правильными грамматиками LL (1) , которые все однозначны.

reinierpost
источник