Преобразование в однозначную грамматику из неоднозначной грамматики

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

s --> [0],s,[1].
s --> [0],s.
s --> [].

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

   s --> [0],s,[1].
   s --> [0],a.
   s --> [].
   a --> [0],a.
   a --> [].

Хорошо? И как я могу это доказать?


grammar prolog dcg ambiguous-grammar
person Vous    schedule 07.04.2014    source источник
comment
0 и 1 — это наш алфавит. [] означает пустой набор и используется на Прологе. Мы пишем S -> 0S1, когда в прологе это s --> [0],s,[1].   -  person Vous    schedule 07.04.2014
comment
Вы понимаете, что такое язык вашей грамматики? Если вам нужен краткий ответ, то да, вы устранили двусмысленность, а вторая форма — однозначная грамматика.   -  person Grijesh Chauhan    schedule 07.04.2014
comment
Это слова из алфавита {1,0}, которые можно составить по этим правилам: S-›0 S 1 ... ?   -  person Vous    schedule 07.04.2014
comment
Нет, S -> 0 S 1 генерирует 0^n1^n, но ваша грамматика генерирует 0^n1^m, где n ›= m   -  person Grijesh Chauhan    schedule 07.04.2014
comment
хотя не существует алгоритмического решения для проверки того, является ли грамматика неоднозначной или нет (и две грамматики эквивалентны). Так что единственный трюк, который у вас есть, - это способность, доказательство путем анализа.   -  person Grijesh Chauhan    schedule 07.04.2014
comment
Да, поэтому, когда я использую второй код из моего сообщения /\, я получаю 0 ^ n1 ^ m, где n >-m :) Но учитель может спросить меня, вы уверены, что это однозначная грамматика?. Вы знаете, легко найти противоречие, но труднее доказать истину.   -  person Vous    schedule 07.04.2014
comment
ОК, надеюсь, я справлюсь с этим. Спасибо за помощь!   -  person Vous    schedule 07.04.2014
comment
Вы должны утверждать, что для каждой строки в языке существует только одно дерево вывода, использующее вашу вторую грамматику. --- Это будет очень длинный ответ. Если я научу вас, как подходить к такого рода вопросам (Возможно, вы можете подождать?) -- Вы понимаете приоритет операторов? или поток генерации?   -  person Grijesh Chauhan    schedule 07.04.2014
comment
Чтобы обосновать свой ответ: скажите своему учителю: в моей второй версии грамматики вы сначала генерируете все 1, а затем, как только вы переходите к s --> [0],a. производству, вы не можете добавить 1 в строку. (и если вы думаете, что 0 nas 1 как оператор, то приоритет 0 выше, чем 1, поскольку он получает позицию ниже в дереве синтаксического анализа). Вы можете прочитать этот ответ чтобы узнать идею приоритета   -  person Grijesh Chauhan    schedule 07.04.2014
comment
Теперь я понимаю. Большое Вам спасибо.   -  person Vous    schedule 08.04.2014

Ответы (1)


arrow_upward
2
arrow_downward

Так как же доказать двусмысленность? В Прологе это легко возможно для конкретных предложений:

| ?- length(Xs,N), bagof(t,phrase(s,Xs),[_,_|_]).              

N = 3
Xs = [0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 5
Xs = [0,0,0,0,1] ? ;

N = 5
Xs = [0,0,0,1,1] ? ;

N = 6
Xs = [0,0,0,0,0,1] ?

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

Однако есть одно предостережение, которое может проявиться только через некоторое время: bagof/3 нужно каким-то образом хранить весь набор решений. Поэтому, если этот набор очень велик, bagof/3 может переполниться. Следующий запрос позволяет избежать этой ошибки за счет получения избыточных решений:

| ?- length(Xs,N), phrase(s,Xs), bagof(t,phrase(s,Xs),[_,_|_]).

N = 3
Xs = [0,0,1] ? ;

N = 3
Xs = [0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 5
Xs = [0,0,0,1,1] ...

с вашей улучшенной грамматикой циклы запросов. Это означает, что система не может найти контрпример. По крайней мере, не с длиной ниже 1000, что я и тестировал.

Некоторые общие замечания о написании DCG на Прологе:

  • Попробуйте поставить рекурсивный регистр последним, это может сэкономить место.

  • Возможно, вы захотите использовать строки в двойных кавычках для представления терминалов. Дополнительную информацию см. в этом ответе.

person false    schedule 17.06.2014