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

Question

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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