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

21

При рассмотрении компьютерных моделей вычислений иерархия Хомского обычно характеризуется (по порядку) конечными автоматами, автоматами со спуском, линейными связанными автоматами и машинами Тьюринга.

Для первого и последнего уровней 1 (обычные языки и рекурсивно перечислимые языки) не имеет значения сила модели, рассматриваем ли мы детерминированные или недетерминированные машины, то есть DFA эквивалентны NFA, а DTM эквивалентны NTM 2 .

Однако для КПК и LBA ситуация иная. Детерминированные КПК распознают строго меньший набор языков, чем недетерминированные КПК. Это также важный открытый вопрос, являются ли детерминированные LBA такими же мощными, как недетерминированные LBA, или нет [1].

Это вызывает мой вопрос:

Существует ли модель машины, которая характеризует языки без контекста, но для которых недетерминизм не добавляет дополнительной мощности? (Если нет, есть ли какое-то свойство КЛЛ, которое предлагает причину для этого?)

Мне кажется маловероятным (для меня), что было бы доказуемо, что контекстно-свободные языки так или иначе нуждаются в недетерминизме, но не существует (известной) модели машины, для которой достаточно детерминированных машин.

Вопрос расширения такой же, но для контекстно-зависимых языков.

Ссылки

  1. S.-Y. Курода, "Классы языков и линейно связанные автоматы" , Информация и управление, 7: 207-223, 1964.

Сноски

  1. Дополнительный вопрос для комментариев: есть ли причина для уровней (упорядоченных по множеству включений) иерархии Хомского быть числами от 3 до 0, а не от 0 до 3?
  2. Чтобы быть понятным, я говорю о языках, которые могут быть признаны только. Очевидно, что такие сложности радикально влияют на вопросы сложности.
formal-languages computability context-free computation-models context-sensitive Люк Мэтисон
источник
1
Итак, вы спрашиваете о классе языков, превышающих (но максимально приближенных) КЛЛ, для которых детерминированная версия = недетерминированная версия?
Райан
@ Райан: нет, я спрашиваю, есть ли модель машины, которая характеризует КЛЛ, но для которой недетерминированные и детерминированные варианты эквивалентны по силе. Однако, если предположить, что нет положительного ответа (что я подозреваю, что нет), это хорошо ответьте на вопрос.
Люк Мэтисон
3
Я думаю, что основная проблема в этом вопросе заключается в отсутствии общего определения «вычислительной модели». Вы можете, например, определить детерминированный TM, снабженный бесконтекстным грамматиком, который принимает слово, если грамматика его генерирует. Это детерминированная модель, которая эквивалентна КЛЛ, но это глупо ...
Шалл
@ Шал, это справедливо, но, похоже, трудно дать определение «разумной» модели. Ваш пример, очевидно, кажется неестественным, но я не думаю, что есть оправданный подход к определению.
Люк Мэтисон
Чтобы связать в последующем вопросе Райана , машина, упомянутая в ответе Томаса Климпеля (хотя и не такая элегантная, как КПК), соответствовала бы идее «естественного» так, как ТМ, ограниченный вычислением CFG, не подходил бы. Возможно, интуиция заключается в том, что TM с CFG явно кодирует в определении CFL, хотя не очевидно, например, что CFG и PDA должны быть связаны, PDA является естественным расширением DFA и работает для CFL. ,
Люк Мэтисон

Ответы:

-2

В моем понимании теории вычислений единственная ситуация, когда недетерминизм не дает вам дополнительной гибкости (т. Е. Мощности), находится на рекурсивно перечислимом / рекурсивном уровне. Это в первую очередь из-за проблемы остановки и ограничений возможностей ТМ в разрешимости, что, как я считаю, отвечает на один из ваших вопросов в примечаниях, а также на боковой панели. Иерархия Хомского является логическим представлением о продвижении последней гибкости (если можно так выразиться), позволяющей машине получить больше мощности. Помогает ли это кому-нибудь из ваших вопросов / мыслей?

Что касается PDA и LBA, я помогу другим опытным людям здесь, в сообществе, помочь с этим, мой опыт был больше с TM и теорией, связанной с более высокой (более RE) частью иерархии (по крайней мере, как преподается в мой старшекурсник).

Теория вычислений Питера Линца

https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241/ref=pd_sbs_14_img_0?_encoding=UTF8&psc=1&refRID=6AA9FQJWZZNZDTQ6Z3K4

BMC
источник
Это не отвечает на вопрос. ОП уже в курсе того, что вы написали.
Юваль Фильмус