Хомская иерархия на простом английском

Question

Я пытаюсь найти простое (то есть неформальное) объяснение 4 уровней формальной грамматики (неограниченная, контекстно-зависимая, контекстно-свободная, регулярная), как изложено Хомским.

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

Answer 1

Может быть, вы получите лучшее понимание, если вспомните автоматы, генерирующие эти языки.

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

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

Контекстно-зависимые языки генерируются с помощью недетерминированных машин Тьюринга с линейной границей. Они знают прошлое и могут иметь дело с различными контекстами, потому что они недетерминированы и могут получить доступ ко всему прошлому в любое время.

Неограниченные языки создаются машинами Тьюринга. В соответствии с тезисами Черч-Тьюринга, машины Тьюринга могут рассчитывать все, что вы можете себе представить (что означает все разрешимо).

Answer 2

Что касается обычных языков, есть много эквивалентных характеристик. Они дают много разных способов смотреть на обычные языки. Трудно дать определение «простым английским», и если вам трудно понять какие-либо характеристики обычных языков, маловероятно, что объяснение «простым английским» поможет. Из определений и различных свойств замыкания следует отметить одну вещь: обычные языки как-то воплощают понятие «конечности». Но это опять-таки трудно оценить без лучшего знакомства с обычными языками.

Считаете ли вы понятие конечного автомата непростым и чистым?

Позвольте мне упомянуть некоторые из множества эквивалентных характеристик (по крайней мере, для других читателей):

• Языки, принятые детерминированными конечными автоматами
• Языки, принятые недетерминированными конечными автоматами
• Языки, принимаемые чередующимися конечными автоматами
• Языки, принятые двусторонними детерминированными конечными автоматами
• Языки, генерируемые леволинейными грамматиками
• Языки, сгенерированные линейно-правильными грамматиками
• Языки, сгенерированные регулярными выражениями .
• Объединение некоторых классов эквивалентности правой конгруэнции конечного индекса .
• Объединение некоторых классов эквивалентности конгруэнции конечного индекса.
• Обратное изображение при гомоморфизме моноида подмножества конечного моноида.
• Языки, выражаемые в монадической логике второго порядка над словами.

Answer 3

Обычный: Эти языки отвечают да / нет с конечными автоматами

Без контекста: На этих языках при заданном входном слове (с использованием состояния и стека) мы всегда можем ответить да / нет, если он является членом языка

Контекстно-зависимый: Пока производство в грамматике никогда не уменьшается (α -> β), мы можем ответить да / нет (используя состояние машины и кусок памяти, который имеет линейный размер с вводом)

Рекурсивно подсчитываемое: Может ответить да, но в случае нет оно перейдет в бесконечный цикл

см. это видео для полного объяснения.