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

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

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

Ответ 1

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

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

Контекст:. Эти языки, когда задано входное слово (с использованием состояния machiene и stack), всегда могут отвечать да/нет, если он является членом языка

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

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

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