Какое значение имеют контекстно-зависимые (тип 1) языки?

Видя, что в иерархии Хомского языки типа 3 могут распознаваться конечным автоматом без внешней памяти (т. Е. Конечным автоматом), тип 2 - конечным автоматом с одним стеком (т. Е. Автоматом с понижением) и тип 0 - конечный автомат с двумя стеками (или, что эквивалентно, лента, как в случае с машинами Тьюринга), как языки типа 1 вписываются в эту картину? И какие преимущества дает определение того, что язык - это не только тип 0, но и тип 1?

Чувствительные к контексту языки - это как раз те языки, которые могут распознаваться машиной Тьюринга с использованием линейного пространства и недетерминизма. Вы можете смоделировать такую ​​машину Тьюринга, используя экспоненциальное время, чтобы вы могли распознать любой такой язык в экспоненциальном времени. Обратите внимание, что проблема распознавания некоторых контекстно-зависимых языков является -завершенной, что означает, что мы почти уверены, что вы не сможете добиться большего успеха, чем экспоненциальное время.$PSPACE$

Сравнивая это тип 0 языков, это означает , что вы можете по крайней мере сказать что - то о том , как долго это берет , чтобы признать язык. Язык типа 0 может даже не быть разрешимым: язык всех машин Тьюринга, которые останавливаются, является языком типа 0, но поскольку распознавание этого языка является именно проблемой остановки, его нельзя решить.

Контекстно-зависимые грамматики не очень полезны на практике. Контекстуально свободные грамматики интуитивно работать, но в качестве примеров на Википедии показывает , контекстуально чувствительные грамматики очень быстро стать довольно грязно. Программы , использующие полиномиальное пространство намного более легко разработаны (и в -полноты гарантирует существование некоторой эквивалентной CSG , который только полиномиально больше пространства использования вашего алгоритма).$PSPACE$

Причина их существования состоит в том, что они образуют очень естественное расширение контекстно-свободных грамматик (вы позволяете контексту определять, какие произведения допустимы). Это, вероятно, вдохновило Хомского определить их и назвать их языками типа 1. Помните, что это определение было сделано до того, как компьютеры стали такими же быстрыми, какими они являются сегодня: оно больше интересует теоретиков формального языка, чем программистов.

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

Вообще говоря, вы обычно хотите знать меньший класс , к которому данный язык принадлежит. Это связано с тем, что более мелкие классы можно распознать / принять / сгенерировать с помощью более простых механизмов (автоматов, грамматик, регулярных выражений и т. Д.), Что является желательным.$L$

$\mathcal{A}$$L(\mathcal{A})$

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

Согласно Википедии , Хомский определил контекстно-зависимые грамматики (то есть Тип 1), чтобы описать синтаксис естественных языков. Это немного отличается от других классов языков, которые были введены для описания семейств строк, которые использовались в математике (например, синтаксис арифметических формул) вместо естественных языков (например, синтаксис грамматически правильного предложения в английском языке) ,

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

Это приводит к интересному свойству, заключающемуся в том, что каждое произведение генерирует подъязык того, который генерируется теми, которые находятся глубже в стеке, и, таким образом, для каждой пары A и B произведений, генерируемых и потребляемых на любом конкретном входе, у нас есть три возможных случая:

• a: вход, потребляемый A, полностью содержится во входе, потребляемом B; или
• б: вход, потребляемый А, полностью содержит вход, потребляемый В; или
• c: вход, потребляемый A, полностью не пересекается с входом, потребляемым B.

Это подразумевает, что следующее никогда не происходит:

• d: вход, потребляемый A, частично перекрывает вход, потребляемый B.

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

В реальном мире контекстно-зависимый язык имеет смысл, например, обозначая <b> полужирный текст </ b>, <i> курсивный текст </ i> и <u> подчеркнутый текст </ u> эти HTML-теги и позволяют им перекрываться, например: «Это <u> текст с <i> смешанными </ u> перекрывающимися тегами </ i>». Заметьте, что для анализа этого и определения, соответствуют ли все начальные теги конечным тегам, PDA не подойдет, потому что он не является контекстно-свободным, но LBA легко это сделает.

Закрытие недвижимости

Из всех языковых классов иерархии Хомского только регулярные и контекстно-зависимые языки закрыты для дополнения . Следовательно, это своего рода уникальная особенность контекстно-зависимых языков.

В отличие от контекстно-свободных языков, CS также закрыты на пересечение и перемешивают продукт .

Любой язык типа 1 может быть распознан машиной Тьюринга, которая использует только линейное пространство (так называемые линейные ограниченные автоматы).

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

Иерархия Хомского классифицирует грамматики больше, чем языки. Однако он не был предназначен для того, чтобы иметь какое-то отношение к количеству лент, которые автомат должен был бы распознать, как вы предлагали для типов 2 и 3, даже если есть некая машина Тьюринга, которая делает это для грамматик типа 1.

Следует также отметить, что языки грамматики типа 0 не все распознаются машиной Тьюринга, но они могут перечисляться только такой машиной: тип 0 означает рекурсивное перечисление, а машины Тьюринга распознают только рекурсивные языки.

Современный язык программирования постоянно использует контекстно-зависимые функции; они попадают в подмножество, которое может быть эффективно решено.

Примерами являются анализ имени и типа и вывод типа.

Многие другие упоминали, что языки типа 1 - это те, которые могут распознаваться линейными ограниченными автоматами. Проблема остановки решаема для линейных ограниченных автоматов, что, в свою очередь, означает, что многие другие свойства, которые в вычислительном отношении неразрешимы для языков, распознаваемых Turning Machines, разрешимы для языков типа 1.

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