Хомская иерархия устарела?

45

Иерархия Хомского (–Schützenberger) используется в учебниках теоретической информатики, но она, очевидно, охватывает только очень небольшую часть формальных языков (REG, CFL, CSL, RE) по сравнению с полной диаграммой зоопарка сложности . Играет ли иерархия какую-либо роль в текущих исследованиях? Я нашел только небольшие ссылки на Хомского здесь, на cstheory.stackexchange, а в Сложностном зоопарке имена Хомский и Шютценбергер вообще не упоминаются.

Является ли текущее исследование более сфокусированным на других средствах описания, кроме формальных грамматик? Я искал практические методы для описания формальных языков с различной выразительностью, и наткнулся на растущий контекстно-зависимый язык (GCSL) и визуально выпадающие языки (VPL), которые лежат между классическими языками Хомского. Не следует ли обновить иерархию Хомского, чтобы включить их? Или нет смысла выбирать определенную иерархию из полного набора классов сложности? Насколько я понимаю, я пытался выбрать только те языки, которые могут вписаться в пробелы иерархии Хомского:

REG (= Chomsky 3) ⊊ VPL ⊊ DCFL ⊊ CFL (= Chomsky 2) ⊊ GCSL Ch CSL (= Chomsky 1) ⊊ R ⊊ RE

Я до сих пор не понимаю, где «мягко контекстно-зависимые языки» и «индексированные языки» подходят (где-то между CFL и CSL), хотя кажется, что они имеют практическое значение для обработки естественного языка (но, может быть, что-то, имеющее практическое значение, менее интересно в теоретических исследованиях ;-). Кроме того, вы могли бы упомянуть GCSL ⊂ P ⊂ NP ⊂ PSPACE и CSL ⊊ PSPACE ⊊ R, чтобы показать отношение к известным классам P и NP.

Я нашел на GCSL и VPL:

  • Роберт Макнотон: вставка в иерархию Хомского? В кн .: Драгоценности - это навсегда, Материалы по теоретической информатике в честь Арто Саломаа. С. 204-212, 1999
  • http://en.wikipedia.org/wiki/Nested_word#References (VPL)

Я также был бы рад, если бы вы знали более свежий учебник по формальным грамматикам, который также имеет дело с VPL, DCLF, GCSL и индексированными грамматиками, предпочтительно с указателями для практических приложений.

Jakob
источник
7
Незначительный момент: я не рассматриваю отсутствие имен Хомский и Шютценбергер в Зоопарке Сложности как свидетельство того, что «иерархия Хомского устарела». Иерархия Хомского - это понятие в теории формального языка. Сложность зоопарк представляет собой веб-сайт в основном о теории сложности, хотя он содержит некоторые понятия в теории формального языка, такие как языки без контекста. Это взаимосвязанные, но разные поля. Это было бы устаревшим, если бы оно не было упомянуто в учебнике по теории формального языка, но я не знаю, так ли это.
Цуёси Ито
7
Хороший вопрос, Цуеши. Честно говоря, я хотел бы увидеть «Зоопарк формальных языков» с хорошим теоретическим обоснованием (ссылки на научные статьи!), Но также и с практическими ресурсами. Например, существуют десятки вариантов синтаксиса Backus-Naur-Form и вариантов регулярных выражений (некоторые из них даже не регулярные). Помимо простой иерархии Хомского, мне было трудно получить четкую картину современного состояния исследований в формальных языках.
Якоб
Вы также можете добавить языки без звездочек строго ниже обычных языков. Они как обычные, но без звезды Клини. Хорошо известно. Хорошо вела себя.
Рен Романо
Как показали несколько ответов, формальные грамматики по-хомски - это исторический метод описания формальных языков, который достиг своих пределов. Я все еще ищу хорошие обзоры формальных грамматик, которые не сосредоточены на теории сложности, но спасибо за все дальнейшие ссылки! Я приму ответ mgalle, потому что у него пока меньше всего репутации.
Якоб
2
В области компьютерных наук разработка компьютерных языков, разработка программного обеспечения и программирование, не зависящие от контекста грамматики и языки, а также регулярные выражения и языки являются основным рабочим оборудованием и так же важны, как и прежде. Но для произвольных грамматик, LBA и контекстно-зависимых языков, с другой стороны, я видел несколько приложений или их вообще нет.
reinierpost

Ответы:

20

Из того, что я видел в сообществе Natural Language Processing, формальные грамматики а-ля Chomsky больше не используются. Они (тоже) считают, что Хомская Иерархия устарела в модельном языке.

Его место заняли такие вещи, как правило переписывания (алгоритм Ларса), модели зависимостей (Дэн Кляйн), грамматика подстановки деревьев (модель DOP), грамматики двоичных объектов (Алекс Кларк).

mgalle
источник
Перечитав мой ответ, он звучит более негативно, чем я хотел, чтобы он тоже звучал. RL и CFL никогда не должны были быть реалистичными моделями естественного языка, и большинство «новых» моделей фактически вдохновлено ими.
mgalle
Я думал, что RL даже не разрабатывался как модель естественных языков, а как модель поведения некоторой системы. [Оригинальный текст Клини также не использует формальную терминологию языка.]
DG_
26

Короче говоря: да.

В частности: Хомский был одним из первых, кто формализовал иерархию, связывающую языки, грамматику и автоматы. Это понимание по-прежнему очень актуально и преподается во всех вводных курсах по теории автоматов. Тем не менее, конкретная иерархия, предложенная Хомским, и названия элементов иерархии уже не имеют значения. С тех пор мы изобрели многочисленные формализмы, которые находятся между уровнями иерархии Хомского, над ней или под ней. И имена, использованные Хомским, не особенно интересны, то есть они не основаны на интересном показателе сложности или чем-то еще, они просто числа. Должны ли языки, чувствительные к контексту, быть Тип-1.5 или Тип-1.7 или Тип-1.3? Какая разница. «Слегка чувствительный к контексту» - это гораздо более информативное имя.

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

Рен Романо
источник
4
Мы нашли лучшие имена, да. Это не означает, что результаты устарели.
Рафаэль
4
@Raphael: Устаревание связано не с именами, а с тем, что специфическая иерархия, введенная Хомским, больше не используется. Включения, описанные иерархией Хомского, (а) все еще верны, и (б) среди включений в любой современной иерархии; но иерархия Хомского как таковая не очень важна, за исключением того, что она попадает в некоторые известные моменты. Люди больше не занимаются исследованиями иерархии Хомского, они проводят исследования в других местах. Это не похоже на полиномиальную башню, которая имеет причины для своих названий / структур.
Рен Романо
26

Если что-то в TCS устарело, именно эта иерархия включения крошечного подмножества классов сложности оказалась известной / интересной в 1956 году.

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

Скотт Ааронсон
источник
12
Как однажды кричал Юрис Хартманис: «А как же классы Хомского? Классы Хомского - мерзость !!»
Райан Уильямс
1
Райан: Я также помню, как Юрис называл CH "мерзостью"! Когда я писал свой ответ, я размышлял, захочет ли он, чтобы его замечание было обнародовано. Но ты знаешь его лучше, чем я ... :-D
Скотт Ааронсон
Этот комментарий также может быть мотивирован, по крайней мере, чуть ли не уничижительным взглядом некоторых теоретических компьютерных наук и математиков на лингвистику и другие «слабые» науки: xkcd.com/435 . Но, конечно, сегодня иерархия Хомского затеняет взгляд на современную теорию сложности, так что это отвечает на мой вопрос. Тем не менее, было бы неплохо иметь некоторую обновленную замену для начала в учебной программе по теории старшекурсников, особенно если вы больше интересуетесь формальными языками и грамматикой для практических приложений.
Якоб
1
В иерархии Хомского перечислены классы языков, упорядоченные по сложности описания, а не по сложности вычислений, что обычно подразумевается при использовании термина «теория сложности». Они связаны, очевидно. Как бы то ни было, я до сих пор не понимаю, как одна (грубая) иерархия может скрывать более утонченные классы, которые вряд ли можно понять, если они не происходят из Хомской Иерархии. Они входная дверь!
Рафаэль
20

Если вы рассматриваете иерархию Хомского с «современными» именами (т. Е. REG, LIN, CFL, CSL, RE или DFA / NFA, PDA, LBA, TM), я скажу: нет, она не устарела!

Причина 0 : Это все еще правильно в том смысле, что его определения и результаты не противоречат новым знаниям.

Причина 1 : Эти классы / модели вычислений все еще являются первыми, кого вы учите, потому что они просты и хорошо изучены. Попробуйте научить LR автомата старшекурснику, не покрывая сначала DFA / DPDA.

Причина 2 : занятия по-прежнему являются первыми / основными ориентирами для новых изобретений (я просмотрел статью о мульти-CFG, в которой, конечно же, говорилось: больше, чем CFG, меньше, чем CSG). Это может быть отчасти потому , что они учат первым, но и потому , что они являются простыми и хорошо изучены.

Анти-причина 3 : результаты не устарели только потому, что были найдены новые классы / модели. Они сохраняют свою ценность как основы области, несмотря на то, что они не используются активно на исследовательской границе.

Рафаэль
источник
10
«Математика не стареет , она становится классикой ». (К сожалению, я не знаю, кому приписывается эта цитата.)
Генрих Апфельм
Разве вы не имеете в виду «NPDA» вместо «DPDA»? Некоторые контекстно-свободные языки распознаются только недетерминированными автоматами.
Zsbán Ambrus
@ ZsbánAmbrus Совершенно верно; Я должен был написать просто «КПК». Благодарность!
Рафаэль
Последняя причина совсем не убедительна (наверное, поэтому это анти-причина?). Множество результатов устарели, потому что их причисляют к другим, а иногда даже упрощают с помощью другого подхода к предмету. Я не говорю здесь об этом, просто причина, о которой говорится, не говорит много. Кроме того, грамматический придира: «устаревший» не глагол.
Сашо Николов
11

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

Следующая иллюстрация может быть полезной:

Редактировать: Формальные языки играют важную роль в разработке компьютерных языков (таких как Java) и компиляторов, а также в обработке естественного языка (NLP).

М.С. Дусти
источник
Извините Андраш, я не могу понять ваш комментарий. ОП спросила, устарела ли Хомская иерархия. Он рассуждал так: он не видел его в зоопарке сложности и т. Д. Я ответил, что если он рассматривает автоматы как модель вычислений, иерархия Хомского становится актуальной. Кроме того, я упомянул, что классы этой иерархии важны для разработки компилятора и алгоритмов NLP. ИМХО, это полностью связано с вопросом.
MS Dousti 17.10.10
2
Конечно, иерархия Хомского на самом деле не устарела, ее можно найти в большинстве представлений теоретической информатики, формальных языков, проектирования компиляторов и т. Д. Но кроме этого, кажется, нет ничего нового, что можно сказать. Я думаю, что языки благодарности между REG и CFL, а также между CFL, также могут быть важны. Является ли просто плохой идеей расширить иерархию этими языками, потому что иерархия Хомского имеет запах «устаревшего», что не важно для текущих исследований?
Якоб
Я не думаю, что это плохая идея, хотя нужно найти какое-то приложение, для которого подходит новое расширение.
MS Dousti 17.10.10