Существуют ли в сущности неоднозначные и детерминированные контекстно-свободные языки?

36

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

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

Примером детерминированного, однозначного языка является язык: Примером недетерминированного, однозначного языка является язык:

{anbn∈{a,b}∗|n≥0}
{w∈{a,b}∗|w=wR}

Из Википедии примером по сути неоднозначного языка без контекста является следующий союз языков без контекста, которые также должны быть контекстно-свободными:

L={anbmcmdn∈{a,b,c,d}∗|n,m≥0}∪{anbncmdm∈{a,b,c,d}∗|n,m≥0}

Теперь по вопросам:

  1. Известно ли, существует ли детерминированный, по сути неоднозначный контекстно-свободный язык? Если так, есть ли (легкий) пример?
  2. Известно ли, существует ли недетерминированный, по сути неоднозначный язык без контекста? Если так, есть ли (легкий) пример?

Ясно, что поскольку существует по сути неоднозначный язык без контекста ( пример ), ответ на один из этих вопросов будет легким, если известно, является ли детерминированным или недетерминированным. Я также предполагаю, что это правда, что если есть детерминированный, то обязательно будет и недетерминированный ... но я был удивлен раньше. Ссылки приветствуются и заранее приносим свои извинения, если это хорошо известный, известный результат (в этом случае я совершенно не знаю об этом).LL

formal-languages automata formal-grammars pushdown-automata Patrick87
источник

Ответы:

30

Если язык является детерминированным, он принимается некоторым детерминированным автоматом, который, в свою очередь, означает, что существует некоторая грамматика LR (1), описывающая язык, и, поскольку каждая грамматика LR (1) однозначна, это означает, что не может быть неоднозначным по своей сути. Кнут доказал это в своей статье, в которой он представил LR (1) ( О переводе языков слева направо ).LL

Язык может быть описан некоторой контекстно-свободной грамматикой тогда и только тогда, когда он может быть распознан каким-то недетерминированным автоматом. Как частный случай этого, по сути неоднозначные контекстно-свободные грамматики могут быть проанализированы некоторым недетерминированным автоматом.

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

Алекс тен Бринк
источник
+1 за ссылку на тот факт, что все детерминированные КЛЛ по своей сути не являются неоднозначными. Фактически, это также отвечает и на другой вопрос: поскольку существует по сути неоднозначный язык, и он не является детерминированным, он должен быть недетерминированным (обратите внимание, что мое определение недетерминированного КЛЛ не является стандартным, поскольку оно исключает детерминированные КЛЛ; это моя вина за неправильное использование терминологии). В любом случае, вы привели пример для вопроса (2) и показали, что вопрос (1) невозможен. Я подожду и посмотрю, если кто-то уточнит, но в противном случае приму это как правильное. Благодарность!
Patrick87
0

читая википедию, ответ и ваш комментарий к ней, повторяйте (Q2), чтобы прямо заявить, что все неоднозначные КЛЛ по своей сути должны быть недетерминированными по стандартному стандартному стандарту (включая ваш собственный пример!). наткнулся на эту ссылку

ВЗН
источник