Иерархия Хомского: грамматики LR (k) против детерминированных CFG? - PullRequest
Новая
       53

Иерархия Хомского: грамматики LR (k) против детерминированных CFG?

0 голосов
/ 22 мая 2018

Мы изучаем chomsky hiearchy в моем введении в курс информатики.Мой профессор упоминал грамматики лрк несколько раз, но в книге их не учат.Насколько я понимаю, они являются подмножеством детерминированных контекстно-свободных грамматик, которые генерируют однозначные языки.Но чем они отличаются от детерминированных CFG?

Вот иерархия Хомского, которую мы рассмотрели в классе с устройствами, распознающими связанную грамматику: 

recursively enumerable - all turing machines
recursive - deciders/TMs that halt on every input
context sensitive - Linear-bounded non-deterministic Turing machine
context free - nondeterministic PDA
deterministic context free - deterministic PDA 
LRK grammar - deterministic PDA
regular - DFAs/NFAs

На отдельной заметке (пожалуйста, дайте мне знать в комментариях, если этовопрос должен быть отдельным постом) - чем линейно-ограниченный недетерминированный механизм Тьюринга отличается от решателей?

1 Ответ

0 голосов
/ 16 декабря 2018

Хитрость здесь в том, что есть две параллельные иерархии, которые связаны, но не совсем одинаковы.Существуют грамматики LR (k) , которые являются классами грамматик с определенными свойствами.Мы знаем, что

LR (0) ⊊ LR (1) ⊊ LR (2) ⊊ ...

То есть, когда вы увеличиваете k, все больше и большеклассы грамматик включены в класс LR (k).

Независимо существуют языки LR (k) , которые являются языками, для которых существует грамматика LR (k) для некоторыхвыбор к.Есть классная теорема от Дона Кнута, которая показывает, что язык имеет грамматику LR (k) для некоторого k тогда и только тогда, когда он имеет грамматику LR (1).Таким образом, в этом смысле языки LR (k) являются «языками, для которых вы можете создать грамматику LR (1)».

Тогда есть детерминированные языки без контекста (DCFL), которые являются языками, для которыхВы можете построить детерминированный КПК.Известно, что DCFL точно такие же, как языки LR (k), то есть язык является детерминированным CFL тогда и только тогда, когда для него существует грамматика LR (1).

Так что же этозначит для иерархии языков?Это выглядит примерно так: от наименее мощного / наиболее ограничивающего к наиболее мощному / наименее ограничивающему:

  • Регулярные языки
    • Описаны линейно-правыми грамматиками, леволинейными грамматиками, DFA,NFA, регулярные выражения и префиксные грамматики
  • Детерминированные КЛЛ
    • Описаны детерминистическими КПК и грамматиками LR (k)
  • (Недетерминированные) КЛЛ
    • Описаны (нед) детерминированными КПК и КФГ.
  • Контекстно-зависимые языки
    • Описаны линейно-ограниченными автоматами и контекстом-чувствительные грамматики
  • рекурсивные языки
    • языки, принятые некоторыми решающими, языки, в которых язык и дополнение рекурсивно перечислимы
  • рекурсивно перечислимые языки
    • языки неограниченной грамматики;языки машин Тьюринга;языки, которые могут быть проверены машинами Тьюринга;языки счетчиков;и т. д.
...